LeetCode: Maximum Subarray

\(\)

Solution with linear scan

Use a variable sum to store current sum of arr(0..index), if sum is less than zero, it’s better to drop the previous sum, set current index as the new starting index.

Time complexity: \(O(N)\)

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int sum = 0;
    int ans = INT_MIN;
    for(int i=0; i<nums.size(); i++) {
      sum = sum > 0 ? sum + nums[i] : nums[i];
      ans = max(ans, sum);
    }
    return ans;
  }
};

Approach with divide and conquer

Just as quick-sort, we divide the array into two parts, then recursive compute the maximum sum for each parts. The tricky operation is merge, we need to loop from m-1 to l to find the possible maximum value in left part, and do the same thing for right part.

Then, we compare lmax, rmax, and ml + mr + nums[m] (which means combine middle with left part and right part).

The overall time complexity is \(O(NlogN)\).

CAPTURE-2020_02_07_maximum-subarray.org_20200207_213009.png

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    return rec(nums, 0, nums.size() - 1);
  }
private:
  int rec(vector<int>& nums, int l, int r) {
    if (l > r) return INT_MIN;
    if (l == r) return nums[l];
    int m = (l + r) >> 1, ml = 0, mr = 0;
    int lmax = rec(nums, l, m - 1);
    int rmax = rec(nums, m + 1, r);
    for (int i = m - 1, sum = 0; i >= l; i--) {
      sum += nums[i];
      ml = max(sum, ml);
    }
    for (int i = m + 1, sum = 0; i <= r; i++) {
      sum += nums[i];
      mr = max(sum, mr);
    }
    return max(max(lmax, rmax), ml + mr + nums[m]);
  }
};
Don't miss out!
Subscribe To Newsletter

Want to be better at coding and CS ?

Programming tutorials

Career advice and tips

......

It's Free!

Invalid email address
Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *