By

已知一个无序整数数组，求数组中连续子序列的最大值
时间复杂度 O(n)
e.g:
[-9, -3, -1, -4, -7, -8] => -1
[2, -1, 0, 3, 8, -5, 9, -12, 10] => 21

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
/*
 * 数组索引为 (0, n - 1)
 * 假设第 i 项到第 i + x 项最大 (i, i + x)  i >= 0 && i <= n - 1 && x >= 0 && x <= n - 1 - i
 * 则 第 i 项到第 i + x - 1 项 的和 肯定 >= 0 并且第 i + x 项 >= 0
 * 即 E(i, i + x - 1) >= 0
 * 先定义两个变量
 * sum(连续 x 项的和) maxSum(最大 连续 y 项的和)
 * 初始化 第一项为最大值
 */
 
function arrMaxSum(arr){
    var sum = arr[0];
    var maxSum = sum;

    for(var i = 1, len = arr.length; i < len; i++){
        if(sum <= 0){
            sum = arr[i];
        }else {
            sum += arr[i];
        }
        maxSum = sum > maxSum ? sum : maxSum;
    }

    return maxSum;
}
console.log(arrMaxSum([1, 2, 3, 4, -11, 12, -4, 5]));  // => 13
console.log(arrMaxSum([-2, -4, -1, -7]));  // => -1