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.

Solution: Dynamic Programming

Keep track of the current maximum

int maxSubArray(vector<int>& nums) {
    int maxSoFar = nums[0];
    int curMax = nums[0];

    for (int i=1; i<nums.size(); i++) {
        curMax = max(nums[i], curMax+nums[i]);
        maxSoFar = max(maxSoFar, curMax);
    }
    return maxSoFar;
}

Solution: Kadane’s Algorithm:

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this).

Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array:
  (a) max_ending_here = max_ending_here + a[i]
  (c) max_so_far = max(max_so_far, max_ending_here)
  (b) max_ending_here = max(0, max_ending_here)
return max_so_far

int maxSubArray(vector<int>& nums) {
    int maxEndingHere = 0, maxSoFar = INT_MIN;
    for (auto num: nums) {
        maxEndingHere = maxEndingHere + num;
        maxSoFar = max(maxSoFar, maxEndingHere);
        maxEndingHere = max(maxEndingHere, 0);
    }
    return maxSoFar;
}