Maximum Product Subarray--LeetCode

柔情只为你懂 2022-08-07 13:35 188阅读 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 条评论，188人围观）

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

相关阅读

相关 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 赞/ 162 阅读

相关 Maximum Product Subarray--LeetCode

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

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

相关 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 赞/ 144 阅读

相关 LeetCode152—Maximum Product Subarray

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

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

相关 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 赞/ 191 阅读

相关 uva 11059 Maximum Product

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

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

相关 628.Maximum Product Of Three Numbers

> Given an integer array, find three numbers whose product is maximum > and output the

布满荆棘的人生/ 2022年05月30日 06:38/ 0 赞/ 147 阅读

相关 628. Maximum Product of Three Numbers

import java.util.Arrays; / Created by Joe on 2018/3/17. 628. Maximum Prod

约定不等于承诺〃/ 2022年05月29日 05:25/ 0 赞/ 160 阅读

相关 11059:Maximum Product

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

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

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

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

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