滑动窗口方法通常可以帮助我们降低蛮力方法的时间复杂度。
问题：
给定一个大小为'n'的整数数组。
我们的目标是计算数组中'k'个连续元素的最大和。
Input : arr[] = {100, 200, 300, 400}
k = 2
Output : 700
|
有两种主要方法可以找到大小为 n 的数组中 k 个连续元素的最大总和：
1、暴力破解：
使用蛮力求解意味着要探索所有可能的情况。此时我们并不关心效率，而是希望得到正确的结果。因此，我们可以运行一个嵌套循环，探索给定数组中所有长度为 k 的窗口，然后选取最大和。
这种方法迭代所有可能的大小为 k 的子数组并计算它们的总和。然后它会跟踪遇到的最大总和。
这是算法：
- 将变量max_sum初始化为负无穷大。
- 循环数组 (n - k + 1) 次：
- 将变量current_sum初始化为 0。
- 从当前索引开始循环 k 次：
- 如果 current_sum大于 max_sum，则更新 max_sum。
- 返回max_sum。
这种方法的时间复杂度为 O(n * k)，因为它会迭代所有可能的子数组。
// BRUTE FORCE :
for(int i = 0; i < n-k+1; i++){
int current_sum = 0;
for(int j = 0; j < k; j++){
current_sum = current_sum + arr[i+j];
}
max_sum = max(current_sum, max_sum); // 如果 current_sum大于 max_sum，则更新 max_sum
}
|
2.滑动窗口：
现在请注意，在计算了第一个窗口（大小为 k）的总和后，为了得到下一个重叠窗口的总和，我们只需要去掉最左边的项目值，然后加上新的（最右边的）项目值，因此我们基本上省去了重新计算窗口非变化部分的总和。
这种方法维护一个大小为 k 的窗口，并通过更新先前的总和而不是从头开始重新计算来有效地计算每个子数组的总和。
这是算法：
- 初始化两个变量：
- max_sum为负无穷大。
- window_sum为前 k 个元素的总和。
- 循环剩余元素 (n - k) 次：
- 从 window_sum 中减去当前索引 - k 处的元素。
- 将当前索引 + (k - 1) 处的元素加入 window_sum。
- 如果 window_sum 大于 max_sum，则更新 max_sum。
- 返回max_sum。
int max_sum = 0, window_sum = 0;
/* calculate sum of 1st window */
for (int i = 0; i < k; i++) window_sum += arr<i>;
/* 在数组中从起点到终点滑动窗口。. */
for (int i = k; i < n; i++){
window_sum += arr<i> - arr[i-k]; // saving re-computation
max_sum = max(max_sum, window_sum); //如果 window_sum 大于 max_sum，则更新 max_sum。
|
我们用内存节省了时间，这是算法中一个非常经典的权衡方法，滑动窗口就是这样的，我们会看到。时间复杂度从 O(n²) 降至 O(n)。
Python代码
要计算整数数组中连续 "k "个元素的最大和，可以使用滑动窗口方法。下面是 Python 中实现这一目的的简单算法：
def max_sum_subarray(arr, k):
n = len(arr)
# 检查 "k "是否大于数组长度
if k > n:
return "Invalid input: k should be less than or equal to the array length."
# 计算前 k 个元素的总和
max_sum = sum(arr[:k])
current_sum = max_sum
# 遍历数组，找出 'k' 个连续元素的最大和
for i in range(k, n):
# 更新当前总和，减去移出窗口的元素
# 并加上进入窗口的新元素
current_sum = current_sum - arr[i - k] + arr<i>
# 如果当前总和大于最大总和，则更新最大总和
max_sum = max(max_sum, current_sum)
return max_sum
# Example usage:
arr = [1, 4, 2, 10, 2, 3, 1, 0, 20]
k = 4
result = max_sum_subarray(arr, k)
print("Maximum sum of", k, "consecutive elements:", result)
|
这种算法的时间复杂度为 O(n)，因为只需遍历数组一次。它使用滑动窗口来有效更新每'k'个连续元素的总和。
Rust代码
fn max_sum_subarray(arr: &[i32], k: usize) -> i32 {
let n = arr.len();
# 检查 "k "是否大于数组长度
if k > n {
panic!("Invalid input: k should be less than or equal to the array length.");
}
// // 计算前 "k "个元素的总和
let mut max_sum = arr.iter().take(k).sum();
let mut current_sum = max_sum;
//遍历数组，找出 'k' 个连续元素的最大和
for i in k..n {
# 更新当前总和，减去移出窗口的元素
# 并加上进入窗口的新元素
current_sum = current_sum - arr[i - k] + arr<i>;
// Update the maximum sum if the current sum is greater
max_sum = max_sum.max(current_sum);
}
max_sum
}
fn main() {
let arr = vec![1, 4, 2, 10, 2, 3, 1, 0, 20];
let k = 4;
let result = max_sum_subarray(&arr, k);
println!("Maximum sum of {} consecutive elements: {}", k, result);
}
|