53.最大子数组和

【题目描述】

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

输入：nums = [5,4,-1,7,8]
输出：23

 【贪心思路】

这个题目一开始想到的是贪心，因为从第一个数字开始，用sum记录当前的数组和是多少，用maxt记录sum数组和是否是最大的，满足则将maxt赋值为sum。其中要注意的是sum和maxt的初始值是0，但是如果遇到数组全部为负数的情况，就会出错，此时要加上一个特判。

【贪心代码】

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxt=0;
        int sum=0;
        int flag=0;
        int x=-100000;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>=0){
                flag=1;
            }
            if(nums[i]>x){
                x=nums[i];
            }
            sum=nums[i]+sum;
            if(sum<0){
                sum=0;
            }
            if(sum>maxt){
                maxt=sum;
            }
        }
        if(flag==0){
            maxt=x;
        }
        return maxt;
    }
};

【分治法思路】

分治法是将一个问题划分为同类型的若干个子问题，然后对子问题求解。

当子问题足够大时，需要递归求解时，我们称之为递归情况（Recursive Case）。当子问题变得足够小，不再需要递归时，表示递归已经“触底”，进入了基本情况（Base Case）

分治法的时间复杂度是O(nlog(n))，空间复杂度是O(long(n))

这个题运用分治法：取数组中心点为中心，最大子序要么在中心左边要么在中心右边，要么跨中心。在中心左边或右边时，可以直接采用递归，跨中心的情况，再分治成中心点左侧和右侧的最大子序和的问题，这个是用贪心解决。

【分治法代码】

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result=0;
        result=maxFun(nums,0,nums.size()-1);
        return result;
    }
    int maxFun(vector<int>& nums,int left,int right){
        //该数组只有一个数的情况
        if(right==left){
            return nums[left];
        }
        int mid=(left+right)/2;
        int rightSum=maxFun(nums,mid+1,right);
        int leftSum=maxFun(nums,left,mid);
        int midSum=midFun(nums,left,mid,right);
        int result=max(rightSum,leftSum);
        result=max(result,midSum);
        return result;
    }
    int midFun(vector<int>& nums,int left,int mid,int right){
        int leftSum=INT_MIN;
        int rightSum=INT_MIN;
        int sum=0;
        for(int i=mid;i>=left;i--){
            sum=sum+nums[i];
            if(sum>leftSum){
                leftSum=sum;
            }
        }
        sum=0;
        for(int i=mid+1;i<=right;i++){
            sum=sum+nums[i];
            if(rightSum<sum){
                rightSum=sum;
            }
        }
        return leftSum+rightSum;
    }
};