最大連續子序列乘積

問題描述 給定一個整數序列（可能有正數，0和負數），求它的一個最大連續子序列乘積。比如給定數組a={3, -4, -5, 6, -2}，則最大連續子序列乘積為720，即3*(-4)*(-5)*6=720。   分析 求最大連續子序列乘積與最大連續子序列和問題有所不同，因為其中有正有負還有可能有0。 假設數組為a[]，直接利用動歸來求解，考慮到可能存在負數的情況，我們用Max[i]來表示以a[i]結尾的最大連續子序列的乘積值，用Min[i]表示以a[i]結尾的最小的連續子序列的乘積值，那麼狀態轉移方程為：        Max[i]=max{a[i], Max[i-1]*a[i], Min[i-1]*a[i]};        Min[i]=min{a[i], Max[i-1]*a[i], Min[i-1]*a[i]}; 初始狀態為Max[0]=Min[0]=a[0]。代碼如下：  

#include"iostream"      
using namespace std;      
  
int max3(int a,int b,int c)  
{  
    int t = a>b?a:b;  
    return t>c?t:c;  
}  
  
int min3(int a,int b,int c)  
{  
    int t = a<b?a:b;  
    return t<c?t:c;  
}  
  
int max_multiple(int *a,int n)    
{    
    int *Min = new int[n]();    
    int *Max = new int[n]();    
    Min[0]= Max[0] = a[0];     
    int max = Max[0];    
    for(int i=1; i<n; i++){    
        Max[i] = max3(Max[i-1]*a[i],Min[i-1]*a[i],a[i]); //求三個數中最大值    
        Min[i] = min3(Max[i-1]*a[i],Min[i-1]*a[i],a[i]); //求三個數中最小值    
        if(max < Max[i])    
            max = Max[i];    
    }    
    //內存釋放    
    delete [] Max;    
    delete [] Min;    
    return max;    
}    
  
//不保存中間變量的實現方法  
int max_multiple_2(int *a,int n)    
{    
    int minsofar, maxsofar, max;    
    max = minsofar = maxsofar = a[0];    
    for(int i=1;i<n;i++){    
        int maxhere = max3(maxsofar*a[i], minsofar*a[i], a[i]);    
        int minhere = min3(maxsofar*a[i], minsofar*a[i], a[i]);    
        maxsofar = maxhere;  
        minsofar = minhere;    
        if(max < maxsofar)    
            max = maxsofar;    
    }    
    return max;    
}    
  
int main()  
{  
    int a[]={3, -4, 0, 6, -2};  
    cout<<max_multiple_2(a,5)<<endl;  
    system("pause");  
    return 0;  
}