LeetCode Q53 Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

先用dp数组创建出一个与已给数组相同长度的array，并且全是0. 让dp array的第一个值为已给数组的第一个值，同时initialize max的值和dp第一个数字的值一样。for loop从第二个位置遍历已给数组，如果dp[ i ] 前面的值是负数，那么直接将已给数组的值加入进dp数组里。如果是正数就将dp[ i - 1] 与已给数组的nums[ i ] 相加，最后比较是max大，还是dp数组现在的这个值大

class Solution
{
   public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int max = nums[0];
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        //两种情况更新 dp[i]
        if (dp[i - 1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = dp[i - 1] + nums[i];
        }
        //更新 max
        max = Math.max(max, dp[i]);
    }
    return max;
}
}