Leetcode/Linkedin -- 53.Maximum Subarray(DP or Dvide&Conquer)

53. Maximum Subarray

• Difficulty: Medium

https://leetcode.com/problems/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.

Company:LinkedIn Bloomberg Microsoft
相关题：http://rainykat.blogspot.com/2017/01/leetcode-121-best-time-to-buy-and-sell.html

关键字： DP，Kadene's algorithm(专解maximum subarray相关题)
专业分析： https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts  

思路： fill dp[i] with current max sum, either itself only or dp[i-] + itself(if dp[i-1]>0)
Complexity： Time O(n) Space O(n)

public class Solution {
    public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];//max sum of arr[0..i]
        for(int i = 1; i < n; i++){
            dp[i] = A[i]+ (dp[i-1]>0?dp[i-1]:0);//in subproblem, A[i] must be contained in max value of current subarray with A[i]
            max = Math.max(max,dp[i]);//max to track the maximum of each max of current subarray A[i]
        }
        return max;
    }
}

Kadene's Algorithm

解法2： 用Kadene's algorithm。 calculate with previous index(max_ending_here), add if res iof A[i-1](max_ending_here)>0, track the end position of max

public class Solution {
    public int maxSubArray(int[] A) {
        int n = A.length;
        
        int max_so_far = A[0],max_ending_here = A[0];
        for(int i = 1; i < n; i++){
            max_ending_here = Math.max(A[i],max_ending_here+A[i]);
            max_so_far = Math.max(max_so_far,max_ending_here);
        }
        return max_so_far;
    }
}