[LeetCode] Maximum Subarray

Problem Statement (link):

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:
Suppose we scan from left to right, each element could either be counted in the max-sum subarray, or not. If we use an array to store this information, we probably could solve the problem in O(n) time.

Thus, the idea is to use DP to solve the problem. Specifically, the DP array stores the maximum sum we have so far if we count the current element in. In addition, we use an integer to store the maximum sum we have so far.

Code:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        if (n==0) return 0;
        int maxSum=INT_MIN; // max sum so far
        vector<int> dp(n+1);  // dp[i+1]: the maxSum of subarray which ends with A[i];
        dp[0]=0;
        for (int i=0; i<n; i++) {
            if (dp[i]<0) dp[i+1]=A[i];
            else dp[i+1]=dp[i]+A[i];
            maxSum=max(maxSum, dp[i+1]);
        }
        return maxSum;
    }
};