﻿ 【数组】Maximum Subarray

### 【数组】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`.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

```/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
var sum=0,maxsum=-2147483648,begin=0;
for(var i=0,len=nums.length;i<len;i++){
if(sum>=0){
sum=sum+nums[i];
}else{
sum=nums[i];
begin=i;
}

if(maxsum<sum){
maxsum=sum;
left=begin;
right=i;
}
}

return maxsum;
};```

```int maxSum1(vector<int>&vec, int &left, int &right)
{
int maxsum = INT_MIN, sum = 0;
for(int i = 0; i < vec.size(); i++)
for(int k = i; k < vec.size(); k++)
{
sum = 0;
for(int j = i; j <= k; j++)
sum += vec[j];
if(sum > maxsum)
{
maxsum = sum;
left = i;
right = k;
}
}
return maxsum;
}```

```int maxSum2(vector<int>&vec, int &left, int &right)
{
int maxsum = INT_MIN, sum = 0;
for(int i = 0; i < vec.size(); i++)
{
sum = 0;
for(int k = i; k < vec.size(); k++)
{
sum += vec[k];
if(sum > maxsum)
{
maxsum = sum;
left = i;
right = k;
}
}
}
return maxsum;
}```

```//求数组vec【start，end】的最大子数组和，最大子数组边界为[left，right]
int maxSum3(vector<int>&vec, const int start, const int end, int &left, int &right)
{
if(start == end)
{
left = start;
right = left;
return vec[start];
}
int middle = start + ((end - start)>>1);
int lleft, lright, rleft, rright;
int maxLeft = maxSum3(vec, start, middle, lleft, lright);//左半部分最大和
int maxRight = maxSum3(vec, middle+1, end, rleft, rright);//右半部分最大和
int maxLeftBoeder = vec[middle], maxRightBorder = vec[middle+1], mleft = middle, mright = middle+1;
int tmp = vec[middle];
for(int i = middle-1; i >= start; i--)
{
tmp += vec[i];
if(tmp > maxLeftBoeder)
{
maxLeftBoeder = tmp;
mleft = i;
}
}
tmp = vec[middle+1];
for(int i = middle+2; i <= end; i++)
{
tmp += vec[i];
if(tmp > maxRightBorder)
{
maxRightBorder = tmp;
mright = i;
}
}
int res = max(max(maxLeft, maxRight), maxLeftBoeder+maxRightBorder);
if(res == maxLeft)
{
left = lleft;
right = lright;
}
else if(res == maxLeftBoeder+maxRightBorder)
{
left = mleft;
right = mright;
}
else
{
left = rleft;
right = rright;
}
return res;
}```