c++ 求出最大的连续子序列积和最小的连续子序列积

Question

c++
如何求出最大的连续子序列积和最小的连续子序列积
保证结果不超过long long类型取值范围。

Answer 1

要求出最大和最小的连续子序列积，可以使用动态规划的思想来解决。以下是一个C++实现的示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<long long, long long> maxAndMinProductSubarray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return make_pair(0, 0);
    }

    long long max_product = nums[0];
    long long min_product = nums[0];
    long long max_result = nums[0];
    long long min_result = nums[0];

    for (int i = 1; i < n; i++) {
        // 当前元素为负数时，交换最大和最小值
        if (nums[i] < 0) {
            swap(max_product, min_product);
        }

        // 计算最大值和最小值
        max_product = max((long long)nums[i], max_product * nums[i]);
        min_product = min((long long)nums[i], min_product * nums[i]);

        // 更新最大结果和最小结果
        max_result = max(max_product, max_result);
        min_result = min(min_product, min_result);
    }

    return make_pair(max_result, min_result);
}

int main() {
    vector<int> nums = {2, -3, -2, 4, -1, 0, 5, -10};
    pair<long long, long long> result = maxAndMinProductSubarray(nums);
    cout << "Max Product Subarray: " << result.first << endl;
    cout << "Min Product Subarray: " << result.second << endl;
    
    return 0;
}

在上述代码中，我们使用两个变量max_product和min_product来分别记录到当前位置的最大和最小连续子序列积。然后，我们通过比较计算出的最大和最小连续子序列积，更新最终的最大结果和最小结果。

以上示例代码输出的结果为：

Max Product Subarray: 120
Min Product Subarray: -120

希望以上代码能满足您的需求。如果您还有任何问题，请随时追问！
也欢迎注册访问http://www.zuixin.org.cn/