c++怎么求最大子數組乘積

本篇內容介紹了“c++怎么求最大子數組乘積 ”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目要求： 給定一個整數數組，求乘積最大的子數組的值。

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

/*
最大子串乘積，由于可能出現負數。也是DP問題，也是局部最優和全局最優問題。
這里需要記錄最小值，假設有兩個數組，分別記錄包括當前元素在內的子串所能構成
的最大和最小值，然后根據這個再更新全局最大，至于當前最大，可能是之前最大
乘以當前元素，也可能是前一個元素最小乘以當前元素，也可能是當前元素 
*/

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++怎么求最大子數組乘積 ”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！