请问老师关于 leetcode 53 号求最大子序和的问题
来源：11-1 结语
Osuribaba
2020-12-08
请教老师一个问题，我在做 leetcode 的 最大子序和 这个问题的时候, 一般的动态规划解法是这个
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
状态转移方程是 res[i] = max(res[i - 1] + nums[i], nums[i]), 我有点不太理解，既然求的是 最大的 “连续” 子数组 的话，res[i - 1] 又表示是 0 ~ (i -1) 的最大子序和, 那咋保证 res[i - 1] + nums[i] 就是连续的呢？
比如说有个数组: [-1, 1, 2, 3, -1, 1], 要求 res[5] 的最大连续和, 那 res[4] 的最大和是，中间的 1 + 2 + 3 = 6, 然后 nums[5] 是 1, 按照转移方程就 res[5] = max(res[4] + nums[5], nums[5]), 那答案应该是 7 呀, 但是中间那 1,2,3 和最后一位的 1 它是不连续的呀。我感觉我好像哪块儿绕进去了，求老师指点，谢谢老师~
1回答
-
res[i - 1] 表示的不是是 0 ~ (i -1) 的最大子序和；res[i - 1] 表示的是，以 nums[i - 1] 结尾的最大子序和，所以 res[i - 1] 一定包含 nums[i - 1] 这个数。
也正因为如此，在你的代码中，我们还需要另外一个 maxAns 来计算真正的最大子序列和，而不是直接返回 pre（如果是你理解的定义，直接返回 pre 就够了）。
res[i] = max(res[i - 1] + nums[i], nums[i]) 的意思是，以 nums[i] 结尾的最大子序列和，或者是在 res[i - 1] 的基础上，再加上 nums[i]，或者以 nums[i] 单起一个新的序列。
你后面举的例子是错误的，因为 res[4] 不可能等于 6。而是等于 5。实际用这个测试用例运行这个程序，试试看？看在每一步，res[i] 具体是多少？
继续加油！：）
012020-12-08
相似问题
回答 2
回答 2