最大子数组和

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

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

示例 3：

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

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题解:

//贪心
class Solution {
public:
    int ans=INT32_MIN;
    int maxSubArray(vector<int>& nums) {
        int count=0;
        for (int i = 0; i < nums.size(); i++)
        {
            count += nums[i];
            if(count>ans) ans=count;
            //可以置0,即使全部都是负数,在上面的if会单独对每一个元素进行比较
            if(count<=0) count=0;
        }
        return ans;
    }
};

//动态规划
class Solution {
public:
    //dp[i] 表示i个位置及其之前的最大连续子数组和
    //这题不能有元素还返回0,就算全负,也要返回一个最大的负数
    int maxSubArray(vector<int>& nums) {
        vector<int>dp(nums.size(),0);
        dp[0] = nums[0];
        int ans=nums[0]; //这里很关键.不能是ans=0,同样是因为上面这个原因
        if(nums.size()==1) return nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
            if(ans<dp[i]) ans=dp[i];
        }
        return ans;
    }
};