Maximum Product Subarray--LeetCode

柔情只为你懂 2022-08-07 13:35 182阅读 0赞

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array `[2,3,-2,4]`,  
the contiguous subarray `[2,3]` has the largest product = `6`.

思路：最大子串乘积，由于可能出现负数。DP问题，也是局部最优和全局最后，不过这里还需要记录最小值，两个数组，分别记录包括当前元素在内的子串所能构成的的最大和最小值，然后根据这个再更新全局最大，至于当前最大，可能是之前最大乘以当前元素，也可能是前一个元素最小乘以当前元素，也可能是当前元素。

当前最小也是一样的道理。

#include <iostream>
    #include <vector>
    #include <string>
    using namespace std;
    
    int maxProduct(vector<int>& vec)
    {
        if(vec.size()==0)
         return 0;
        vector<int> maxcur(vec.size(),0);
        vector<int> mincur(vec.size(),0);
        maxcur[0]=vec[0];
        mincur[0]=vec[0];
        int maxproduct = vec[0];
        int i,temp;
        for(i=1;i<vec.size();i++)
        {
           maxcur[i] = max(vec[i],max(maxcur[i-1]*vec[i],mincur[i-1]*vec[i]));
           mincur[i] = min(vec[i],min(mincur[i-1]*vec[i],maxcur[i-1]*vec[i]));
           
           maxproduct = max(maxcur[i],maxproduct);                      
                               
        }
        return maxproduct;
        }
    
    int main()
    {
        int array[]={2,3,-2,4};//,-1,-2,4,-2,5,-1,2};
        vector<int> vec(array,array+sizeof(array)/sizeof(int));
        cout<<maxProduct(vec)<<endl;
        system("pause");
        return 0;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has

淩亂°似流年/ 2022年08月21日 00:21/ 0 赞/ 160 阅读

相关 Maximum Product Subarray--LeetCode

Find the contiguous subarray within an array (containing at least one number) which has

柔情只为你懂/ 2022年08月07日 13:35/ 0 赞/ 183 阅读

相关 318. Maximum Product of Word Lengths

Given a string array `words`, find the maximum value of `length(word[i]) length(word[j]

迷南。/ 2022年07月29日 11:50/ 0 赞/ 142 阅读

相关 [leetcode]152. Maximum Product Subarray -- JavaScript 代码

/ @param {number[]} nums @return {number} / var maxProduct = function(nums) {

冷不防/ 2022年07月17日 02:13/ 0 赞/ 162 阅读

相关 LeetCode152—Maximum Product Subarray

原题 [原题链接][Link 1] > Find the contiguous subarray within an array (containing at leas

快来打我*/ 2022年07月15日 05:06/ 0 赞/ 143 阅读

相关 [UVA11059]Maximum Product 暴力求解入门

[\[UVA11059\]Maximum Product\[暴力\]][UVA11059_Maximum Product] 题意：给出一个序列，问这个序列中最大连续累乘的子序

谁践踏了优雅/ 2022年07月10日 10:00/ 0 赞/ 150 阅读

相关 leetcode: 628. Maximum Product of Three Numbers

1.题目 Given an integer array, find three numbers whose product is maximum and output t

淩亂°似流年/ 2022年06月13日 11:12/ 0 赞/ 187 阅读

相关 uva 11059 Maximum Product

题目解析：题目的意思十分简单，首先输入一个数n，紧接着下面输入n个数，求子串的最大乘积，如果最大乘积小于0，直接输出0；题目解析：这是一个简单的模拟题，十

左手的ㄟ右手/ 2022年06月10日 01:57/ 0 赞/ 151 阅读

相关 11059:Maximum Product

[Maximum Product][] include<bits/stdc++.h> using namespace std; const int m

不念不忘少年蓝@/ 2022年01月06日 16:39/ 0 赞/ 175 阅读

相关 [leetcode]动态规划之Maximum Product Subarray

动态规划之Maximum Product Subarray 题目思考类型归类代码题目 [leetcode入口][leetcode]

女爷i/ 2021年09月28日 14:52/ 0 赞/ 298 阅读