发布于个人公众号，打开微信，搜索
MelodyJerry即可## 53. 最大子序和
LeetCode官方的难度定位为简单，个人觉得可以达到中等的！！！
| 难度 | 简单 | 通过率 | 54.64% (571,167/1,045,196) |
|---|
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示：
- 1 <=
nums.length<= 3 ∗ 1 0 4 3 * 10^4 3∗104 -
−
1
0
5
-10^5
−105 <=
nums[i]<= 1 0 5 10^5 105
进阶：
如果你已经实现复杂度为 O ( n ) O(n) O(n) 的解法，尝试使用更为精妙的
分治法求解。
题解
① 动态规划
- 值得注意的是题目描述中是
连续，所以这里直接用动态规划就可以AC了。 - 状态转移方程：
-
dp[i] = max(dp[i-1] + nums[i], nums[i])-
dp[i]： 以nums[i]结尾的子数组的和的最大值
-
- 为什么是
dp[i-1]+nums[i]？- 思考
dp[i-1]是否会对nums[i]带来负增益 - 若带来负增益，自然是
nums[i]值比dp[i-1]+nums[i]值更大
- 思考
- 初始条件：
dp[0] = nums[0]
-
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-urKgsuGc-1626534999894)(https://gitee.com/melodyjerry163/filebed/raw/master//carbon(2)].png)
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0]; // 初始条件
int max = dp[0];
for (int i = 1; i < nums.length; i++) {
/** 状态转移方程:
* dp[i] = max(dp[i-1] + nums[i], nums[i])
* dp[i]: 以nums[i]为右区间的子数组的和的最大值
*/
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
/* 等价于
if (dp[i - 1] >= 0)
dp[i] = dp[i - 1] + nums[i];
else
dp[i] = nums[i];
*/
max = Math.max(max, dp[i]); //更新max
}
return max;
}
}
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( n ) O(n) O(n)
② 优化后的动态规划
这个优化主要是减少了空间复杂度
在上面的状态转移方程中提到：
- 为什么是
dp[i-1]+nums[i]？
- 思考
dp[i-1]是否会对nums[i]带来负增益，若带来负增益，自然是nums[i]值比dp[i-1]+nums[i]值更大
再看看代码中的这段注释：
/* 等价于
if (dp[i - 1] >= 0)
dp[i] = dp[i - 1] + nums[i];
else
dp[i] = nums[i];
*/
关键就是这里了，这里就很好地解释了那个思考：
- 思考
dp[i-1]是否会对nums[i]带来负增益 ？
因此根据这段代码，可以对上面的动态规划做个小优化，
- 关键在于
sum>=0这个判断- 当
sum<0时候，对当前的新整数num一定会造成负增益- 即
sum+num一定<了num - 所以最大子数组的和一定不会再继续加当前整数
- 即
- 当
class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE; // 这是个注意点
int sum = 0;
for (int num : nums) {
if (sum >= 0)
sum += num;
else
sum = num;
max = Math.max(max, sum); //更新max
}
return max;
}
}
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( 1 ) O(1) O(1)
另一个版本的优化，其实也差不多的，容易理解。
该算法更为简便之处是忽略了对子序列的寻找比较，而是根据规律直接找出最佳答案。
对于含有正数的序列而言，最大子序列肯定是正数，所以头尾肯定都是正数。我们可以从第一个正数开始算起，每往后加一个数便更新一次和的最大值；当当前和成为负数时，则表明此前序列无法为后面提供最大子序列和，因此必须重新确定序列首项。
class Solution { public int maxSubArray(int[] nums) { int maxSum = 0 , thisSum = 0; for( int i = 0; i < nums.length ; i++ ){ thisSum += nums[i]; if(thisSum > maxSum) maxSum = thisSum; else if(thisSum < 0) thisSum = 0; } return maxSum; } }
③ 分治法
- 其实就是它的
最大子序和要么在左半边，要么在右半边，要么是在中间。 - 对于
左、右边的序列，情况也是一样，因此可以用递归处理。- 递归的基本边界：
左、右为相同位置的元素，即只有一个元素.
- 递归的基本边界：
-
中间部分的则可以直接计算出来。
以下是LeetCode官方题解的分治算法：
class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;
public Status(int lSum, int rSum, int mSum, int iSum) {
this.lSum = lSum;
this.rSum = rSum;
this.mSum = mSum;
this.iSum = iSum;
}
}
public int maxSubArray(int[] nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
}
public Status getInfo(int[] a, int l, int r) {
if (l == r) {
return new Status(a[l], a[l], a[l], a[l]);
}
int m = (l + r) >> 1;
Status lSub = getInfo(a, l, m);
Status rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
public Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = Math.max(l.lSum, l.iSum + r.lSum);
int rSum = Math.max(r.rSum, r.iSum + l.rSum);
int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
}
时间复杂度： O ( n ) O(n) O(n)
空间复杂度： O ( l o g n ) O(log\,n) O(logn)
建议阅读一下李威威同学的经典动态规划问题（理解「无后效性」）