最大連續乘積字串

首先解釋一下字串和子序列的區別：

子串：連續

子序列：不連續

問題描述：給定一個浮點數序列，取最大乘積連續子串的值。

輸入：-2.5,4,0,3,0.5,8,-1

輸出：3,0.5,8

解決這個問題的思路兩個：

一、暴力

二、動態規劃

第一種思路就不分析了。對於動態規劃，假定給定的浮點數組為a[]，考慮到可能有負數，可以用MaxA來表示以a結尾的最大的連續子串的乘積值，用MinA表示以a結尾的最小的子串的乘積值，動態規劃函數如下：

MaxA[i]=Max{a[i],MaxA[i-1]*a[i],MinA[i-1]*a[i]}

MinA[i]=Min{a[i],MinA[i-1]*a[i],MaxA[i-1]*a[i]}

初始狀態為MaxA[0]=MinA[0]=a[0]

完成的代碼如下：

//最大乘積子串
double funcMax(double *a,const int n)
{
 double *MaxA=new double();
 double *MinA=new double();
 MaxA[0]=MinA[0]=a[0];
 double value=MaxA[0];
 for(int i=1;i<n;i++)
 {
  MaxA[i]=max(max(a[i],MaxA[i-1]*a[i]),MinA[i-1]*a[i]);
  MinA[i]=min(min(a[i],MaxA[i-1]*a[i]),MinA[i-1]*a[i]);
  value=max(value,MaxA[i]);
 }
 return value;
}

int main()
{

 double a[]={-2.5,4,0,3,0.5,8,-1};
 double result=funcMax(a,7);
 cout<<result<<endl;
 return 1;
}

----------------------------END----------------------------