一、题意
给出一个整数数组 nums ，求连续相加的最大值（相邻下标加在一起），包括单个元素的情况。
二、解法
贪心算法。
解法一：
从头相加，并保存最大值，如果相加结果小于0，则sum=0。
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
解法二（分治法）：
将数组分成l到mid，mid+1到r，分别求出最大值，然后再根据l到mid到r，跨区域求出最大值，比较三个的大小。
三、代码
1、解法一
int maxSubArray(vector<int>& nums) {
int maxSum = INT_MIN;
int n =nums.size();
int sum = 0;
for(int i=0;i<n;i++){
sum += nums[i];
maxSum = max(sum,maxSum);
sum = sum<0?0:sum;
}
return maxSum;
}
2、解法二（自己写的超时了，官方的也超时了）