发布于个人公众号,打开微信,搜索
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
提示:
nums.length
<=
3
∗
1
0
4
3 * 10^4
3∗104nums[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官方题解的分治算法:
来源:最大子序和 - 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)
建议阅读一下李威威同学的经典动态规划问题(理解「无后效性」)