[LeetCode]Maximum Subarray

Question
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

本题难度Medium。

【复杂度】
时间 O(N) 空间 O(1)

【思路】
为了求整个字符串最大的子序列和，我们将先求较小的字符串的最大子序列和。这里我们从后向前、从前向后计算都是可以的。在从前向后计算的方法中，我们将第i个元素之前最大的子序列和存入变量​​​sum​​​中，对第i+1个元素来说，它的值取决于​​sum​​​，如果​​sum​​是负数，那就没有必要加上它，因为这只会拖累子序列的最大和。如果是正数就加上它。

【注意】
第4、5行别写成：

int ans=0;
int sum=0;

【代码】

public class Solution {
    public int maxSubArray(int[] nums) {
        int size=nums.length;
        int ans=nums[0];
        int sum=nums[0];
        //invariant
        for(int i=1;i<size;i++){
            sum=(sum>0)?sum+nums[i]:nums[i];
            ans=Math.max(ans,sum);
        }
        //ensure
        return ans;
    }
}

参考

​​[Leetcode] Maximum Subarray 子序列最大和​​