leetcode53. 最大子序和
题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解法一，贪心算法：
由第一个元素开始，求连续子数组的和；如果加上某一个元素后数组各元素和大于等于零，则数组增加，并更新最大值；否则以这个元素的下一个元素开始重新构造子数组
class Solution {
public:
int maxSubArray(vector& nums) {
int ret=nums[0];
int sum=nums[0];
for(int i=0;i=0) {
i++;//数组长度增加
if(iret) ret=sum;//更新最大值
}
else{
i++;
if(iret) ret=sum;//更新最大值
}
}
return ret;
}
};
解法二，动态规划：
class Solution {
public:
int maxSubArray(vector& nums) {
int size=nums.size();
vector dp(size);//dp[i]表示nums数组中以nums[i]结尾的最大子序和
dp[0]=nums[0];
int ret=dp[0];
for(int i=1;i 解法三，暴力解法：
使用两层for循环，时间复杂度为O(n2)
解法四，分治算法：
将数组以mid为界分为左右两部分和跨mid部分，并递归求其最大子序和并取其最大值
class Solution {
public:
int maxSubArray(vector& nums) {
int size=nums.size();
int ret=INT_MIN;
ret=maxSubArrayHelper(nums,0,size-1);
return ret;
}
int maxSubArrayHelper(vector nums,int left,int right){
if(left==right) return max(nums[left],nums[right]);
int mid=(left+right)/2;
int leftmax=maxSubArrayHelper(nums,left,mid);
int rightmax=maxSubArrayHelper(nums,mid+1,right);
int midmax=maxmidArray(nums,left,right,mid);
int ret=max(leftmax,rightmax);
ret=max(ret,midmax);
return ret;
}
int maxmidArray(vector nums,int left,int right,int mid){
int leftret=INT_MIN;
int rightret=INT_MIN;
int sum=0;
for(int i=mid;i>=left;i--){
sum+=nums[i];
leftret=max(sum,leftret);
}
sum=0;
for(int j=mid+1;j<=right;j++){
sum+=nums[j];
rightret=max(sum,rightret);
}
return leftret+rightret;
}
};