贪心---最大子序和 Posted on 2021-08-07 00:00:00 2021-08-07 00:00:00 by Author 摘要 这是简单题吗，你搁这里逗我尼，你好奇知道是什么题吗？要不进来看看呗！！！ # 最大子序和 1. 题目描述 - 给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 - **提示：** - `1 <= nums.length <= 3 * 104` - `-105 <= nums[i] <= 105` 2. 示例描述 - 示例一 ``` 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 ``` - 示例二 ``` 输入：nums = [-100000] 输出：-100000 ``` - 示例三 ``` 输入：nums = [1] 输出：1 ``` 3. 解题思路 - 看到这题难度为简单，我觉得解决这道题分分钟的事，然后我陷入了沉思! 思考了30分钟我一行代码没写出来，我又陷入了沉思，最后我心里一万个马飞过，这是简单题吗？想了许久想想还是看看题解吧，看完题解之后，我感觉自己就是个XX。 - 首先，我分析一下自己在做这道题目卡壳的地方。第一就是找到连续的子序列，使得和最大。我在想如果数组某个位置出现负数，那么这个数就不能要了，但是如果出现这种情况[4,-3,6]，那么按照我的想法最大的和是6，事实上结果为7，因为出现负数的地方前后左右数都是正数，这就使得有时候出现负数的元素有时候还得要。所以就一直纠结这种情况。第二种情况就是，数组种前几个元素可以组成最大的和，但是中间一段都是负数，后一段也有可能出现比前一段连续子序列和的最大值大的子序列。我当时就是卡在这两个地方，出不来了。 - 看了题解后发现，这是一道贪心算法，然后我的理解是这样的，首先当遇到一个元素的时候，可以和之前子序列的和相加，如果相加后的值比之前子序列和都要大，那么该元素就可以使用了，就可以加入本次的子序列集合中，如果之前子序列的和与当前元素相加后，变成负数了，那么该元素是负数，并且其绝对值比之前子序列的和都要大，那么该元素的加入会使得之前的子序列和变小，那么本次的子序列就从这里断开，继续寻找下一个和更大的连续子序列。（这里为什么要断开尼，因为题目要求是连续的子序列）。最后直到遍历完整个数组后，就可以找到最大的连续子序列了。具体思想见下面的代码。 4. 代码示例 ```java public int maxSubArray(int[] nums) { //最终结果 int result =nums[0]; //定义一个局部子序列和的最大值的变量 int sum=0; for (int i = 0; i < nums.length; i++) { //局部和与当前数组元素和 sum+=nums[i]; //如果大于之前的局部子序列的和，那么这个元素可以要 if(sum>result){ result=sum; } //如果子序列加入这个元素使得整个子序列和变成负数了，说明这个元素不能要了 //又因为保证子序列是连续的，所以本次的子序列就从这里断开，下一个元素又是重新的一个子序列 //所以这里sum置为0 if(sum<=0)sum=0; } //返回数组中连续子序列和最大值 return result; } ```
{{ item.content }}
{{ child.content }}