c++怎么求最大子數(shù)組乘積

本篇內(nèi)容介紹了“c++怎么求最大子數(shù)組乘積 ”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

題目要求： 給定一個(gè)整數(shù)數(shù)組，求乘積最大的子數(shù)組的值。

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

/*
最大子串乘積，由于可能出現(xiàn)負(fù)數(shù)。也是DP問題，也是局部最優(yōu)和全局最優(yōu)問題。
這里需要記錄最小值，假設(shè)有兩個(gè)數(shù)組，分別記錄包括當(dāng)前元素在內(nèi)的子串所能構(gòu)成
的最大和最小值，然后根據(jù)這個(gè)再更新全局最大，至于當(dāng)前最大，可能是之前最大
乘以當(dāng)前元素，也可能是前一個(gè)元素最小乘以當(dāng)前元素，也可能是當(dāng)前元素 
*/

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};
	vector<int> vec(array,array+sizeof(array)/sizeof(int));
	cout<<maxProduct(vec)<<endl;
	return 0;
}

“c++怎么求最大子數(shù)組乘積 ”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！