aboutsummaryrefslogtreecommitdiff
path: root/max_subarray.cpp
blob: 735692547a56110b4a85a397a3dff989c1e63d5f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "leetcode.h"

class Solution {
public:
  int maxSubArray(vector<int> &nums) {
    return helper(nums, 0, nums.size() - 1);
  }

private:
  int helper(vector<int> &nums, int l, int r) {
    if (l > r)
      return INT_MIN;
    int m = l + (r - l) / 2, mL = 0, mR = 0;
    int lMax = helper(nums, l, m - 1);
    int rMax = helper(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]);
  }
};

int main() {
  vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  Solution obj;
  cout << obj.maxSubArray(nums);
}