力扣.128 最长连续系列 longest-consecutive-sequence
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 -104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
看到连续子数组和，比较自然的是想到用前缀和来加速子数组和的计算。
1）构建好前缀和
2）穷举所有可能的子数组和，找出最大值。
class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
int[] prefixSum = new int[n];
prefixSum[0] = nums[0];
for(int i = 1; i 超出时间限制
204 / 210 个通过的测试用例
我们之所以很慢，是因为在计算连续子数组和的时候，计算了各种场景。但是这里要如何优化呢？
但是不对比所有的，如何找到最大的呢？
最气人的是题目中的那一句：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
感觉双指针不可行 双指针适合计算最大的长度，但是不太适合这种最大的和。
看了一眼相似题目，其中有一个是 【买卖股票的最佳时机】{简单}
于是贪心的话，思路可以简化为：
public int maxSubArray(int[] nums) {
final int n = nums.length;
// BF 匹配
int maxSum = nums[0];
for(int i = 1; i = 0) {
maxSum += num;
} else {
// 如果不是呢？
// 也不能贸然丢弃 因为连续起来，后来可能又大于0的？
// 那么 怎么简单的判断这个事情呢？
}
}
return maxSum;
}
首先看到一首打油诗 被逗笑了
打开我的题库，调为简单难度。
计算最大子数，直接给我难住。
报错铺满屏幕，凝望没有思路。
缝缝补补做出，击败零个用户。
翻阅评论找补，令我勃然大怒。
不禁心有一问，都是人，凭什么我——这么废物。
55555555
被打开的不单单是评论区的，当然还有自己的思路。
我们整体的方向没错，但是这里需要一个技巧。
如下：
/**解题思路
用 temp 记录局部最优值，用 result 记录全局最优值。
每遍历一个新元素时，判断（已遍历的连续子数组的和）加上（当前元素值），与（当前元素值）对比谁更大。
（1）如果已遍历的连续子数组的和 + 当前元素值 >= 当前元素值
说明（已遍历的连续子数组的和）是大于等于0的，令 temp = 已遍历的连续子数组的和 + 当前元素值。
（2）如果已遍历的连续子数组的和 + 当前元素值 class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
// BF 匹配
int maxSum = nums[0];
int tempSum = nums[0];
for(int i = 1; i = 0) {
tempSum += num;
} else {
// 历史和小于 0，直接舍弃。只保留今天
tempSum = num;
}
maxSum = Math.max(maxSum, tempSum);
}
return maxSum;
}
}
简单的优化，我们直接判断是否大于等于0即可，减少一次累加计算。聊胜于无。
1ms 100%
效果拔群
那么这一题和股票有啥关系呢？
股票的买卖贪心其实要简单一些，就是明天比今天高，直接无脑买卖。而且不要求连续。
这里要求连续，就需要一个巧妙的构思，有时候不一定能很快想到。
比如我们可买卖股票无限次数上点难度，增加一个限制，买卖的天数必须是连续的天数，怎么解？
其实就是 {买+卖} 的和当做一个数，然后就变成这一题了
一个问题能不能被 DP 解决呢？
就看能不能拆分为递推的子问题。
那么，这个问题可以吗?
也就是我们还是需要想到上面那个思路。
dp[i] = Math.max(0, dp[i-1]) + nums[i];
class Solution {
public int maxSubArray(int[] nums) {
final int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int maxResult = nums[0];
for(int i = 1; i 2ms 36.91%
DP 的优点是使用范围更加广泛，这如果是一个系列的题目，不断上难度，DP 也许可以成为一个模板。
但是如果是性能，比不上上面的 greedy。
或者说上面的贪心，是对下面递推数组的存储空间优化。
差点挂在了第一个选择的数组题目上....ORZ
登录查看全部
参与评论
手机查看
返回顶部