求乘积最大的连续子数组

这是一个经典的算法问题，可以使用动态规划来解决。这里给出一个基于动态规划的算法：

首先定义两个变量 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 是数组的长度。

相关问题

错误 1 error C2039: “max”: 不是“std”的成员 c:\users\xunuo\documents\visual studio 2013\projects\连续子数组最大乘积\连续子数组最大乘积\源.cpp 16 1 连续子数组最大乘积

这个错误是由于在代码中使用了"max"函数，但是编译器无法找到该函数的定义。根据错误提示，这个函数不是"std"命名空间的成员。

解决这个问题的方法是使用正确的命名空间来调用"max"函数。在C++中，"max"函数位于"algorithm"头文件中，所以你需要在代码中包含该头文件，并使用"std"命名空间来调用"max"函数。

示例代码如下：

#include <algorithm>

int main() {
    int a = 10;
    int b = 20;
    int maxNum = std::max(a, b);
    return 0;
}

在这个示例中，我们包含了"algorithm"头文件，并使用"std::max"来调用"max"函数。

求乘积最大的连续子数组的完整代码

下面是求乘积最大的连续子数组的完整代码：

#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。