Description

Given an array of integers, find a contiguous subarray which has the largest sum.

Notice

The subarray should contain at least one number.

Example

Given the array[−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray[4,−1,2,1]has the largest sum =6

Solution

1. prefix的思路：max[i][j] = sum[0][j] - min[0][i]. ==> sum[i] = sum[i-1] + nums[i]; max = Math.max(max, sum[i] - min); min = Math.min(min, sum[i]);
   注意初始化不能写成sum[0] = 0 (sum[n+1]), max = Integer.MIN_VALUE, min = Integer.MAX_VALUE, 因为假如nums[0] < 0，在计算max=sum[0]-min时max会溢出成Integer.MAX_VALUE.

2. 一维动归：dp[i]表示包含第i个元素的所有subarray中最大的元素和。状态方程dp[i] = max(dp[i-1] + nums[i], nums[i])

1.
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        int max = nums[0] - 0;
        int min = Math.min(sum[0], 0);

        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i-1] + nums[i];
            max = Math.max(max, sum[i] - min);
            min = Math.min(min, sum[i]);
        }

        return max;
    }
}

2.
public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
           for (int i = 1; i < nums.length; i++) {
               dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
               max = Math.max(dp[i], max);
           }

           return max;
    }
}