看看 Leetcode #53（最大子陣列，https ://leetcode.com/problems/maximum-subarray/ ），我在評論中看到了這個解決方案，并調整了我的代碼。不過有一部分我不明白——有人可以解釋一下嗎？
我希望用滑動視窗方法解決它。
class Solution {
public:
int maxSubArray(vector<int>& nums) { // runtime O(n), space O(1)
int largestSum = nums[0];
int windowSum = 0;
// int windowStart = 0;
for (int windowEnd = 0; windowEnd < nums.size(); windowEnd ) {
windowSum = nums[windowEnd];
if (nums[windowEnd] > windowSum) { // if the value at this index is greater than the running sum up to and including this index, abandon the running sum and restart the sliding window from here.
windowSum = nums[windowEnd];
// windowStart = windowEnd; is essentially what we are doing
}
if (windowSum > largestSum) { // the window has at least 1 number
largestSum = windowSum;
}
}
return largestSum;
}
};
我很困惑，如果我們遇到一個單獨的值大于運行總和，我們放棄運行總和的原因是什么。有人可以解釋為什么這種方法對我有用嗎？也許舉一兩個例子？不明白為什么這不會跳過潛在的滑動視窗。
uj5u.com熱心網友回復：
代碼寫得不好，掩蓋了它的操作。在您詢問的 if 條件中，唯一可能為真的方法是在回圈迭代開始之前總和是否為負。這就是它真正重新啟動以回應：一個整體無用的前綴。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/390704.html
下一篇：洗掉陣列中重復的連續值