• 欢迎访问小杰博客网站
  • 欢迎访问小杰博客网站哦

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

未分类 小杰 4年前 (2015-03-11) 193次浏览 已收录 1个评论
  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. }  

最大子数组和 写法类似哈



小杰博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:【面试经典算法】最大子数组乘积
喜欢 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址