Maximum Subarray

Q:

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.

T:
Traverse the array. Continue adding new elements to the sum. Record the max sum once seeing a larger one. When seeing a negative number, we also add it to the sum, as long as the sum is positive. Once the sum becomes negative, we reset the sum to zero since the max sum should not include the elements before whose sum is negative.

A:

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int sum = 0;
        int max = INT_MIN;
        for(int i=0; i < n; i++) {
            sum+=A[i];
            if(sum > max) {
                max = sum;
            }
            if(sum < 0) {
                sum = 0;
            }
        }
        return max;
    }
};