# C++ simple O(n) solution with DP and Divide and conquer solution

• ``````    //*******************************************
// solution 1   using dynamics programming
// Time complexity : O(n)
// Space complexity : O(n)
// save the maximum value ended in i in a array maxVal[i]
``````
``````    int maxSubArray(vector<int>& nums) {

if (nums.size() < 1)
return INT_MIN;
vector<int> maxVal(nums);
int best = maxVal[0];

for (int i = 1; i < maxVal.size(); ++i) {
if (maxVal[i - 1] > 0)
maxVal[i] += maxVal[i - 1];
best = max(maxVal[i],best);
}
return best;
}
``````
``````    //***********************************************
// solution 2, using divide and conquer method
// Divide array into three part: left part, right part, and crossing part
// Time complexity: O(nlogn)
// Space complexity: O(1)
``````
``````int maxSubArray(vector<int>& nums) {
if (nums.size() < 1)
return INT_MIN;
return maxSubArrayHelper(nums, 0, nums.size() - 1);

}
int maxCrossSubArray(vector<int>& nums, int l, int m, int h) {
// maximum value in the left part of midpoint (including midpoint)
int left_part = INT_MIN;
int right_part = INT_MIN;
for (int i = m, sum = 0; i >= l; --i) {
sum += nums[i];
left_part = max(sum, left_part);
}
// maximum value in the right part of midpoint
for (int i = m + 1, sum = 0; i <= h; ++i) {
sum += nums[i];
right_part = max(sum, right_part);
}

return left_part + right_part;
}

int maxSubArrayHelper(vector<int>& nums, int l, int h) {
if (l == h)
return nums[l];
int m = (h - l) / 2 + l;
int left_max = maxSubArrayHelper(nums, l, m);
int right_max = maxSubArrayHelper(nums, m + 1, h);
int cross_max = maxCrossSubArray(nums, l, m, h);
return max(max(left_max,right_max),cross_max);
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.