53. 最大子数组和(Java) Leecode

解题思路：

动态规划问题，利用dp数组。

dp[ i ] 只与dp[i - 1] 有关。
所以要构建dp数组，再比大小。

这里有个优化方法，在构建dp数组的时候，就直接比较子数组大小。

class Solution {
    public int maxSubArray(int[] nums) {

        int n = nums.length;
        if(n == 0) return 0;

        //base case
        int dp_0 = nums[0];
        int dp_1;
        int res = dp_0; //记录子数组大小

        //在构建dp数组的时候，比较最大值
        for(int i = 1; i < n ; i++){
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;
            res = Math.max(res, dp_1);
        }

        return res;
    }
}