济南做网站公司xywlcn竞价推广开户

题目

给你一个整数数组 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 定义dp数组的含义，dp[i]为从以下标i结束的连续数组的最大和
2 接着推导出递推公式，想要得到dp[i]有两种途径

第一个就是加上当前元素了，即dp[i] = dp[i - 1] + nums[i]
第二个就是没有将当前元素加到序列中，而是从当前元素开始新的子数组即dp[i] = nums[i]

3 接下来分析一下初始化，一维的dp数字全都初始化为0，这是肯定的，因为dp[i]一开始确实没有一个固定的值
第一个dp[i] = dp[i - 1] + nums[i]，所以i要从1开始遍历，不然会访问内存错误，dp[0]需要单独初始化为nums[0]

class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();vector<int> dp(len + 1, 0);dp[0] = nums[0];int result = dp[0];for(int i = 1; i < len; i ++){dp[i] = max(dp[i - 1] + nums[i], nums[i]);if(dp[i] > result) result = dp[i];}return result;}
};``````cpp
class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;//最大和int count = 0;//当前和for(int i = 0; i < nums.size(); i ++){count += nums[i];if(count > result){result = count;}if(count < 0) count = 0;}return result;}
};

贪心

贪心是从局部最优推导全局最优

那么这道题的局部最优在哪里呢？

如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是局部最优的地方！

所以思路关键在于：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;//最大和int count = 0;//当前和for(int i = 0; i < nums.size(); i ++){count += nums[i];if(count > result){result = count;}if(count < 0) count = 0;}return result;}
};