最大连续乘积字串

首先解释一下字串和子序列的区别：子串：连续子序列：不连续问题描述：给定一个浮点数序列，取最大乘积连续子串的值。输入：-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----------------------------本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-09/107309.htm