問題：求「長度為 k」的子陣列的最大數字總和。
舉例：{1, -1, 5, -2, 3}，k = 3，答案為 6。
{1, -1, 5} = 5
{-1, 5, -2} = 2
{5, -2, 3} = 6
原始作法
時間複雜度：O(n2)。
#include <iostream>
#include <climits>
using namespace std;
int main() {
int n = 5, k = 3;
int a[n] = {1, -1, 5, -2, 3};
int ans = INT_MIN;
for(int i=0; i<n-k+1; i++){
int sum = 0;
for(int j=i; j<i+k; j++){
sum += a[j];
}
ans = max(ans, sum);
}
cout << ans;
}Sliding Window
作法：不重新計算每個子陣列的總和，而是使用先前的總和，每次加上最右側，減去最左側。
時間複雜度：O(n)。
#include <iostream>
using namespace std;
int main() {
int n = 5, k = 3;
int a[n] = {1, -1, 5, -2, 3};
int sum = 0;
for(int i=0; i<k; i++) sum += a[i];
int ans = sum;
for(int i=k; i<n; i++){
sum += a[i]; // 加入最右側
sum -= a[i-k]; // 移除最左側
ans = max(ans, sum);
}
cout << ans;
}