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.

Can you also solve it using divide and conquer?

Solution:
Brute-Force: O(N^2) time. Choose any i < j, such that the sub-array begins at i and end at j.
O(N): 1-d dynamic programming: dp[i+1] = max( dp[i] + A[i], A[i] ).

public class Solution {
    public int maxSubArray(int[] A) {
        int maxSum = -Integer.MAX_VALUE;
        int sum = 0;
        int dp_prev = 0;
        for(int i = 0; i < A.length; i++){
            sum = i == 0 ? A[i] : Math.max(dp_prev + A[i], A[i]);
            if(sum > maxSum) maxSum = sum;
            dp_prev = sum;
        }
        return maxSum;
    }
}