leetcode 53. 最大子数组和

53. 最大子数组和

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

法一

1.假如全是负数，那就是找最大值即可，因为负数肯定越加越大。

2.如果有正数，则肯定从正数开始计算和，不然前面有负值，和肯定变小了，所以从正数开始。

3.当和小于零时，这个区间就告一段落了，然后从下一个正数重新开始计算(也就是又回到 2 了)。而 dp 也就体现在这个地方。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum = 0,size = nums.size(); //当前最大连续子序列和为sum
        for(int i = 0;i < size;i++){
            if(sum > 0)  sum += nums[i];//如果sum>0，则说明sum对结果有增益效果，则sum保留并加上当前遍历数字
            else  sum = nums[i];//如果sum<=0，则说明sum对结果无增益效果，需要舍弃，则sum直接更新为当前遍历数字
            maxSum = max(maxSum , sum);//如果这一轮循环的nums[i]是负数，sum就可能变小了，所以需要和maxSum比大小
        }
        return maxSum;
    }
};

法二

使用额外空间

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxRes = nums[0],size = nums.size();
        int dp[size];//dp[i]代表以第 i 个数结尾的「连续子数组的最大和」
        dp[0] = nums[0];
        for(int i = 1; i < size; i++){
            //不是dp[i]=max(dp[i-1],dp[i-1]+nums[i]);而是dp[i]=max(nums[i],dp[i-1]+nums[i]);
            dp[i] = max(nums[i], dp[i-1] + nums[i]);
            maxRes = max(maxRes, dp[i]);
        }
        return maxRes;
    }
};

法三：递归分治法

class Solution {
public:
    int max3(int num1,int num2,int num3){
        return max(num1,max(num2,num3));
    }

    int maxCrossingSum(vector<int>& nums, int left, int mid, int right){
        //考虑第 3 部分跨越两个区间的连续子数组的时候，由于 nums[mid] 与 nums[mid + 1] 一定会被选取
        //可以从中间向两边扩散，扩散到底选出最大值
        int sum = 0;
        int leftSum = INT_MIN;
        // 左半边包含 nums[mid] 元素，最多可以到什么地方
        // 走到最边界，看看最值是什么
        // 计算以 mid 结尾的最大的子数组的和
        for(int i = mid;i >= left;i--){
            sum += nums[i];
            if(sum > leftSum)  leftSum = sum;
        }
        sum = 0;
        int rightSum = INT_MIN;
        // 右半边不包含 nums[mid] 元素，最多可以到什么地方
        // 计算以 mid+1 开始的最大的子数组的和
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum)  rightSum = sum;          
        }
        return leftSum + rightSum;
    }

    int maxSubArraySum(vector<int>& nums,int left,int right){
        if(left == right)  return nums[left];
        int mid = left + (right - left) / 2;//可以很好地防止溢出
        //连续子序列的最大和主要由这三部分子区间里元素的最大和得到：
        //第 1 部分：子区间 [left, mid]；
        //第 2 部分：子区间 [mid + 1, right]；
        //第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。
        //对这三个部分求最大值即可。
        return max3(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid+1, right), maxCrossingSum(nums, left, mid, right));
    }

    int maxSubArray(vector<int>& nums) {
        return maxSubArraySum(nums,0,nums.size()-1);
    }
};