【面试经典算法】最大子数组乘积

1. /*  
2.  给定一个浮点数数组，有正有负数，0，正数组成,数组下标从1算起  
3.  求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1  
4.  用Max[i]表示以a[i]结尾乘积最大的连续子序列  
5.  用Min[i]表示以a[i]结尾乘积最小的连续子序列  因为有复数，所以保存这个是必须的  
6. */    
7. void longest_multiple(double *a,int n){    
8.  double *Min=new double[n+1]();    
9.  double *Max=new double[n+1]();    
10.  double *p=new double[n+1]();    
11.  //初始化    
12.  for(int i=0;i<=n;i++){    
13.   p[i]=-1;    
14.  }    
15.  Min[1]=a[1];    
16.  Max[1]=a[1];    
17.  double max_val=Max[1];    
18.  for(int i=2;i<=n;i++){    
19.   Max[i]=max(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);    
20.   Min[i]=min(Max[i-1]*a[i],Min[i-1]*a[i],a[i]);    
21.   if(max_val<Max[i])    
22.    max_val=Max[i];    
23.  }    
24.  if(max_val<0)    
25.   printf(“%d”,-1);    
26.  else    
27.   printf(“%d”,max_val);    
28. //内存释放    
29.  delete [] Max;    
30.  delete [] Min;    
31. }  

最大子数组和 写法类似哈