Maximum Subarray

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.

Analysis

DP problem：

1. State: max subarray sum end at nums[i]
2. Transfer:
   • if f[i-1]>0, include previous subarray, f[i]=f[i-1]+nums[i]
   • if f[i-1]<0, do not include previous subarray, f[i]=nums[i]
   • summarize, f[i] = max(nums[i],nums[i]+f[i-1])
3. Initial: f[0]=nums[0]
4. Return: maximum number from f[0] to f[len-1]

Code

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        f[0] = nums[0];
        int max=f[0];

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

        return max;
    }
}