力扣52-最大子序和（java详细题解）

本文主要是介绍力扣52-最大子序和（java详细题解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://leetcode.cn/problems/maximum-subarray/description/

前情提要：

因为本人最近都来刷贪心类的题目所以该题就默认用贪心方法来做。

贪心方法：局部最优推出全局最优。

如果一个题你觉得可以用局部最优推出全局最优，并且没有反例来反驳的话就可以用贪心来试试。

题目思路：

我们首先要找出局部最优。

该题是求最大的子数组和。

我们怎么知道他是最大的呢?

如果一个和它是负数，它加上另一个数，只会让这个数变的更小。

这显然是不行的，我们要求最大的子序和，并且这个子序是连续的。

所以当一个连续和为负数时，我们应该直接放弃前面的连续和，找下一个值。

但是这里要想一个极端状况，如果数组给的值全是负数，那么我们找最小的负数即可。

本题局部最优：当一个连续和为负数时，我们应该直接放弃前面的连续和，找下一个值。

全局最优，选取最大的连续和。

具体代码还有一些细节，我放在代码里面讲。

最终代码：

class Solution {public int maxSubArray(int[] nums) {//这里result必须是记录最小值 如果初始化为0，碰巧该数组全为负数，那么就不会更新result了。int result = Integer.MIN_VALUE;//sum记录连续和int sum = 0;//遍历每一个数for(int i = 0;i < nums.length;i ++){sum += nums[i];//result用来更新最大值if(sum > result)result = sum;//如果连续和为负数 那么后面加的数就会让后面的数更小//所以我们直接跳过负数的连续和，让下一个数作为连续和的开头 确定我们这个数组的起始位置//终止位置怎么确定 我们用result常量用来记录每次连续和加上的最大值 也就间接确认这个数组的起始位置了if(sum < 0){//当连续和为负数时，直接在本层循环值赋为0，那么下一层循环sum就等于他本身，也就到达下一数了sum = 0;}   }return result;}
}