从这道题开始，贪心题比较难！最大子数组和扣题链接：https://leetcode-cn.com/problems/maximum-subarray给定一个整数数组nums，找到一个和最大的连续子数组（该子数组至少包含一个元素），返回它的最大总和。示例：输入：[-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组[4,-1,2,1]的和最大，也就是6.暴力解暴力解的思路是第一层for是设置起始位置，第二层for循环遍历数组寻找最大值时间复杂度：O(n^2）空间复杂度：O(1)classSolution{public:intmaxSubArray(vector&nums){intresult=INT32_MIN;intcount=0;for(inti=0;iresult?count:result;}}returnresult;}};上面的暴力解决方案C++能勉强通过，其他语言就不确定了。贪心解贪心在哪里？如果-2+1在一起，计算起点的时候一定要从1开始计算，因为负数只会降低和，这就是贪心的地方！局部最优：当前“连续和”为负数时，立即放弃，从下一个元素开始重新计算“连续和”，因为负数加上下一个元素“连续和”只会越来越小。全局Optimum：选择最大的“连续和”局部最优，记录最大的“连续和”，即可推导出全局最优。从代码上看：遍历nums，从头开始累加count，如果count一旦变为负数加到nums[i]，那么应该从nums[i+1]开始，从0开始累加count，因为已经变成负数了，count，只会拖累sum。这相当于不断调整的起始位置暴力解中的最大子序列和区间。那么有同学问了，是不是不需要调整区间的结束位置呢？怎样才能得到最大的“连续和”呢？如果计数达到最大值，则真正及时记录间隔的结束位置。例如下面的代码：if(count>result)result=count;这相当于用result记录最大子序列和区间和（变相调整终止位置）。如动画所示：最大子序列和红色的起始位置是greedy每次计数为正数时，开始统计一个区间。那么不难写出下面的C++代码（关键地方已经注释了）size();i++){count+=nums[i];if(count>result){//取区间内累加的最大值（相当于连续确定最大子序列的结束位置）result=count;}if(count<=0)count=0;//相当于重新设置最大子序列的起始位置，因为遇到负数必须降低和}returnresult;}};时间复杂度：O(n)空间复杂度：O(1)当然，题目并没有说如果数组为空，应该返回什么，所以如果数组为空，它可以返回任何东西。很多同学认为，如果输入的case全是-1或者全是负数，那么这个贪心算法的结果就会是0，这又是一个证明脑模拟不靠谱的经典案例。我建议您运行代码并尝试一下。试试看，你就会知道，你也会明白为什么result要初始化为最小的负数。动态规划当然这道题也可以用动态规划来做。目前的《CodeCaprice》主要讲解的是贪心系列，后面动态规划系列的时候会详细讲解这道题的dp方法。然后先给出我的dp代码如下，有时间的可以提前做：classSolution{public:intmaxSubArray(vector&nums){if(nums.size()==0)return0;vectordp(nums.size(),0);//dp[i]表示包括i之前的最大连续子序列dp[0]=nums[0];intresult=dp[0];for(inti=1;iresult)result=dp[i];//result保存dp[i]的最大值}returnresult;}};时间复杂度：O(n)空间复杂度：O(n)总结这道题的贪心思想其实我觉得不好，这个有待进一步验证，别看贪心理论很直白，有时候看似是常识，但是贪心题一点都不简单！后面要介绍的贪心题挺难的，哈哈，所以贪心很有意思，不要小看贪心！其他语言版本JavaclassSolution{publicintmaxSubArray(int[]nums){if(nums.length==1){returnnums[0];}intsum=Integer.MIN_VALUE;intcount=0;for(inti=0;iint:result=-float('inf')count=0foriinrange(len(nums)):count+=nums[i]ifcount>result:result=countifcount<=0:count=0returnresultGofuncmaxSubArray(nums[]int)int{maxSum:=nums[0]fori:=1;inums[i]{nums[i]+=nums[i-1]}ifnums[i]>maxSum{maxSum=nums[i]}}returnmaxSum}
