注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时间记录器

记录我的Linux、Android学习之路

 
 
 

日志

 
 

最大子序列和 ZZ  

2012-08-16 13:05:10|  分类: C语言相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

From: http://blog.163.com/lichunliang1988116@126/blog/static/2659944320124115795/

1.求一个序列的最大子序列和的算法时间复杂度为O(n^3),即枚举算法,也就是说:将原序列的每个子序列枚举出来并求和,最后从中找出一个最大值,算法如下:

        long maxSubSum(const long  *a) 

       long max = 0; 

       for (int i = 0; i < a.size(); i++) 

       { 

              for (int j = i; j < a.size(); j++) 

              { 

                     long sum = 0; 

   

                     for (int k = i; k <= j; k++) 

                     { 

                            sum += a[k]; 

                     } 

                     if (sum > max) 

                            sum = Sum; 

              } 

       } 

       return max; 

} 

2. 时间复杂度为O(n^2)。此算法是先在以第i个元素a[i]开始(包含a[i])的子序列中找到一个最大子序列和,然后再从这些最大子序列和中找出最大的一个子序列和,即为原序列的最大子序列和。

    long maxSubSum(const long *a) 

       long max = 0; 

       for (int i = 0; i < a.size(); i++) 

       

              long sum = 0;

              for (int j = i; j < a.size(); j++) 

              {

                        sum += a[j];

                        if(sum > max)

                                 max = sum;  

              } 

       

       return max; 

} 

3. 时间复杂度为O(nlgn)。此算法主要采用了"分治思想",一个序列的是最大子序列出现的位置只有三种情况:i) 在原序列的最左半部分,ii)在原序列的最右半部分,iii)横跨序列中部的占据序列左右两个部分。前两种情况递归求解,第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)以及后半部分最大和(包含后半部分的第一个元素)相加而得到。

long maxSumRec(const long *a, int l, int r) 

       if (l == r) 

       { 

              if (a[l] > 0) 

                     return a[l]; 

              else 

                     return 0; 

       } 

       int center = (l + r) / 2; 

       long maxLeftSum = maxSumRec(a, l, center); 

       long maxRightSum = maxSumRec(a, center+1, r);

       //求出以左边最后一个数字为尾的序列最大值 

       long maxLeftBorderSum = 0, leftBorderSum = 0; 

       for (int i = center; i >= l; i--) 

       { 

              leftBorderSum += a[i]; 

              if (leftBorderSum > maxLeftBorderSum) 

                     maxLeftBorderSum = leftBorderSum; 

       }

       //求出以右边第一个数字开始的序列最大值 

       long maxRightBorderSum = 0, rightBorderSum = 0; 

       for (int j = center+1; j <= r; j++) 

       { 

              rightBorderSum += a[j]; 

              if (rightBorderSum > maxRightBorderSum) 

                     maxRightBorderSum = rightBorderSum; 

       } 

        //返回三者中的最大值

       return max(maxLeftSum, maxRightSum,  

              maxLeftBorderSum + maxRightBorderSum); 

   

long maxSubSum(const long *a) 

       return maxSumRec(a, 0, a.size()-1); 

}

//求出三个long中的最大值 

long max(long a, long b, long c) 

       if (a < b) 

       { 

              a = b; 

       } 

       if (a > c) 

              return a; 

       else 

              return c; 

}

4. 时间复杂度为O(n). 此算法是一个线性时间的算法,程序较为简单,但是不容易理解其正确性。简单地说,最大子序列不可能以和为负数的子序列为前缀的。

long maxSubSum(const long *a) 

       long max = 0, sum = 0; 

       for (int j = 0; j < a.size(); j++) 

       

             sum += a[j]; 

              if (sum > max ) 

                     max = sum; 

              else if (sum < 0) 

                     sum = 0; 

       

       return max ; 

}

还有一种算法时间复杂度也是O(n),但是需要额外的空间开销:

long maxSubSum(const long *a) 

       long b[a.size()];

       b[0] = a[0];

       long max = b[0];

       for (int j = 1; j < a.size(); j++) 

       

              b[j] = ((b[j-1] + a[j]) > a[j])? b[j-1] + a[j] : a[j];              

              if (b[j] > max ) 

                     max = b[j]; 

       } 

       return max ; 

}

  评论这张
 
阅读(237)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017