2905 窗口乘积
大约 2 分钟
2905 窗口乘积
【算法】 滑动窗口
【C++】 滑动窗口、long long
【难度】 入门
一、题目简述
给定 个正整数,求所有长度为 的连续子数组的乘积的最大值。
数据范围:,。
二、解题思路
仍然是定长滑动窗口,但维护的是乘积而非和。
滑动窗口维护乘积:
注意除法必须是整除(因为题目保证为正整数,且窗口右移时一定会除掉之前乘进去的元素)。同时,做到"先除后乘"可以有效避免中间结果溢出。
为什么用 long long? 最坏情况 ,乘积是 ,这个数字远超任何整数类型的范围。但题目通常不会让乘积大到溢出(否则必须用高精度或取模)。假设数据范围合理,乘积能用 long long 容纳,使用 long long 即可。
手动模拟 [1, 2, 3, 4, 5, 6],k=3:
| 步骤 | 窗口范围 | 窗口元素 | 操作 | prod | ans |
|---|---|---|---|---|---|
| 初始 | [1, 3] | 1, 2, 3 | 1×2×3 | 6 | 6 |
| 右移 | [2, 4] | 2, 3, 4 | 6÷1×4 | 24 | 24 |
| 右移 | [3, 5] | 3, 4, 5 | 24÷2×5 | 60 | 60 |
| 右移 | [4, 6] | 4, 5, 6 | 60÷3×6 | 120 | 120 |
最大乘积 = 120。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
// 第一个窗口的乘积
long long prod = 1;
for (int i = 1; i <= k; i++) prod *= a[i];
long long ans = prod;
// 滑动窗口
for (int i = k + 1; i <= n; i++) {
prod = prod / a[i - k] * a[i]; // 先除后乘,减少溢出风险
ans = max(ans, prod);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,遍历一次。
- 空间复杂度:,用于存储数组
a。
五、易错点
- 溢出问题:必须使用
long long,int很容易溢出。若 和 较大,long long也可能不够,此时需要考虑题目是否有取模要求。 - 除法顺序:建议 先除后乘(
prod / a[i-k] * a[i]),虽然数学上等价于先乘后除,但先除后乘能减少中间值的大小,降低溢出风险。 - 保证整除:题目给的元素是正整数,且
a[i-k]一定是之前乘进去的因子,所以整除必定能除尽。
