1 /* 2 A="2,9,-1,3,7,0,8,9,-3",求最大连续乘积子串，有三种方法，方法一：采用动态规划方法，最容易理解，也最容易实现，方法二：同样采用动态规划的 3 思路，但是不用保存两个数组空间。方法三：采用记录最大值，最小值的方法 4 */ 5  6 /* 7 动态规划方法,，两个数组，最大和最小，max[i]以i结尾的序列中最大连续乘积。 8 maxnum[i]=max{maxnum[i-1]*A[i],minnum[i-1]*A[i],A[i]}; 9 minnum[i]=min{maxnum[i-1]*A[i],minnum[i-1]*A[i],A[i]};10 maxnum[0]=minnum[0]=A[0];11 */12 #include <iostream>13 using namespace std;14 #include <string>15 #include <algorithm>16 double maxmultiply(const double *  str,int n)17 {18     int size=n;19     if(size==0)20         return 0;21     double * maxnum=new double[size];22     if(maxnum==NULL)23         exit(1);24     double * minnum=new double[size];25     if(minnum==NULL)26         exit(1);27     double result=str[0];28     maxnum[0]=minnum[0]=str[0];29     for(int i=1;i<n;i++)30     {31         maxnum[i]=max(max(maxnum[i-1]*str[i],minnum[i-1]*str[i]),str[i]);32         minnum[i]=min(min(maxnum[i-1]*str[i],minnum[i-1]*str[i]),str[i]);33         if(maxnum[i]>result)34             result=maxnum[i];35     }36     delete[] maxnum;37     delete[] minnum;38     return result;39 }40 41 /*42 采用动态规划的思路，但是采用两个变量保存max序列和min序列。43 */44 double maxmultiply2(const double * A,int n)45 {46     if(A==NULL)47         return 0;48     double result=A[0];49     double maxnum=A[0],minnum=A[0];50     for(int i=1;i<n;i++)51     {52         double tmpmax=maxnum*A[i];53         double tmpmin=minnum*A[i];54         maxnum=max(max(tmpmax,tmpmin),A[i]);55         minnum=min(min(tmpmax,tmpmin),A[i]);56         if(maxnum>result)57             result=maxnum;58     }59     return result;60 }61         62 //方法三，采用类似观察归纳的方法，maxcurrent,mincurrent ,maxproduct,minproduct ,注意maxcurrent如果小于1要变成1，其实就是好能跟自己比较63 //其实还是一样的，没啥必要写64 double  maxmultiply3(const double * A,int n)65 {66     if(A==NULL)67         return 0;68     double maxcurrent=1;69     double mincurrent=1;70     double maxproduct=1;71     double minproduct=1;72     for(int i=0;i<n;i++)73     {74         maxcurrent*=A[i];75         mincurrent*=A[i];76         if(maxcurrent>maxproduct)77             maxproduct=maxcurrent;78         if(mincurrent>maxproduct)79             maxproduct=mincurrent;80         if(maxcurrent<minproduct)81             minproduct=maxcurrent;82         if(mincurrent<minproduct)83             minproduct=mincurrent;84         if(mincurrent>maxcurrent)85             swap(mincurrent,maxcurrent);86         if(maxcurrent<1)87             maxcurrent=1;88     }89     return maxproduct;90 }91             92 int main()93 {94     double  A[]={-2.5,4,0,3,0.5,8,-1};95     int n=7;96     cout<<maxmultiply3(A,n)<<endl;97     system("pause");98 }