leetcode/js/53-maximum-subarray.js at master · magicly/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
const assert = require('assert');
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = Number.NEGATIVE_INFINITY, max2 = 0;
  let min = Number.NEGATIVE_INFINITY;
  let hasPositive = false;
  for (let num of nums) {
    if (num < 0) {
      min = Math.max(min, num);
    } else {
      hasPositive = true;
    }
    if (max2 + num > 0) {
      max2 += num;
    } else {
      max2 = 0;
    }
    max = Math.max(max, max2);
  }
  if (max === 0 && !hasPositive) max = min;
  return max;
};

var maxSubArray = function (nums) {
  let max = Number.NEGATIVE_INFINITY, max2 = 0;
  for (let num of nums) {
    max2 += num;
    if (max2 > max) {
      max = max2
    }
    if (max2< 0) {
      max2 = 0;
    }
  }
  return max;
};

var maxSubArray2 = function (nums) {
  let maxSoFar = Number.NEGATIVE_INFINITY, maxEndingHere = 0;
  for (let num of nums) {
    maxEndingHere = Math.max(maxEndingHere + num, num);
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }
  return max;
};


console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
assert(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) === 6);
console.log(maxSubArray([-1, -1]));
assert(maxSubArray([-1, -1]) === -1);
assert(maxSubArray([-2, -1]) === -1);
assert(maxSubArray([0]) === 0);
assert(maxSubArray([-1, 0]) === 0);