求乘积最大的连续子数组
时间: 2023-07-24 16:30:28 浏览: 65
这是一个经典的算法问题,可以使用动态规划来解决。这里给出一个基于动态规划的算法:
首先定义两个变量 max_so_far 和 min_so_far,分别表示当前已经扫描过的子数组中乘积最大值和最小值。然后遍历数组,对于每个元素,更新这两个变量,如果当前元素为正数,则 max_so_far 和 min_so_far 分别乘上当前元素,否则交换这两个变量的值再乘上当前元素。最后,max_so_far 中存储的即为最大乘积。
下面是具体的实现代码:
```
int maxProduct(vector<int>& nums) {
int n = nums.size();
int max_so_far = nums[0], min_so_far = nums[0], ans = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] < 0) {
swap(max_so_far, min_so_far);
}
max_so_far = max(nums[i], max_so_far * nums[i]);
min_so_far = min(nums[i], min_so_far * nums[i]);
ans = max(ans, max_so_far);
}
return ans;
}
```
该算法的时间复杂度为 O(n),其中 n 是数组的长度。
相关问题
求乘积最大的连续子数组的完整代码
下面是求乘积最大的连续子数组的完整代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProduct(vector<int>& nums) {
int n = nums.size();
int max_so_far = nums[0], min_so_far = nums[0], ans = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] < 0) {
swap(max_so_far, min_so_far);
}
max_so_far = max(nums[i], max_so_far * nums[i]);
min_so_far = min(nums[i], min_so_far * nums[i]);
ans = max(ans, max_so_far);
}
return ans;
}
int main() {
vector<int> nums = {2, 3, -2, 4};
cout << maxProduct(nums) << endl; // 输出 6
return 0;
}
```
在这个例子中,我们使用了输入数组 `nums = {2, 3, -2, 4}` 进行测试,输出应该为 6。
键盘输入求乘积最大的连续子数组的完整代码
下面是键盘输入求乘积最大的连续子数组的完整代码:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProduct(vector<int>& nums) {
int n = nums.size();
int max_so_far = nums[0], min_so_far = nums[0], ans = nums[0];
for (int i = 1; i < n; i++) {
if (nums[i] < 0) {
swap(max_so_far, min_so_far);
}
max_so_far = max(nums[i], max_so_far * nums[i]);
min_so_far = min(nums[i], min_so_far * nums[i]);
ans = max(ans, max_so_far);
}
return ans;
}
int main() {
vector<int> nums;
int n, x;
cout << "请输入数组长度 n: ";
cin >> n;
cout << "请输入数组元素: ";
for (int i = 0; i < n; i++) {
cin >> x;
nums.push_back(x);
}
cout << "最大乘积为: " << maxProduct(nums) << endl;
return 0;
}
```
在这个例子中,我们使用键盘输入数组,然后调用 `maxProduct` 函数求出最大乘积。