Leetcode53 Maximum Subarray

Posted on

问题描述

给定一个整数数组，找到连续序列和最大的子序列（至少包括一个数字）
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解决方案

1
2
3
4
5
6
7
8
9
10
var maxSubArray = function(nums) {
    var cur = nums[0];
    var sum = nums[0];
    for(var i = 1;i<nums.length;i++){
        sum = sum + nums[i];
        sum = sum>nums[i]?sum:nums[i];
        cur = sum>cur?sum:cur;
    }
    return cur;
};

关键思路之Kadane Algorithm（子序列可以为空）

1
2
3
4
5
6
7
8
9
10
11
//Kadane Algorithm
var maxSubArray = function(nums) {
    var cur = 0;
    var sum = 0;
    for(var i = 0;i<nums.length;i++){
        sum = sum + nums[i];
        sum = sum>0?sum:0;
        cur = sum>cur?sum:cur;
    }
    return cur;
};

1.遍历数组，在遍历过程中，将遍历到的元素累加，当累加结果小于或等于0时，从下一个元素开始，重新开始累积
2.累加过程中，用一个变量记录cur当前最大值
3.一次遍历后,cur即为最大子片段的和值
注意：题目隐含设定是最大子片段可以为空，空片段的和值是0.
理解此算法的关键：
1.最大子片段中不可能包含求和值为负的前缀。因此当计算出一个负值时，要从当前值重新算起。
2.另一关键是所有出现过的最大值都会被记录

本题关键

1.子序列至少包含一个元素，与Kadane Algorithm不同
2.最大值可能为负，因此sum初始值不为0，sum应与当前元素大小比较，而非0