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 }
