经典算法——求最大子序列和

《经典算法——求最大子序列和》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、经典算法——求最大子序列和比较经典的算法问题，能够很好的体现动态规划的实现，以一点“画龙点睛”大大精简了算法复杂度，且实现简单。本文中实现了4种:一般maxSubSequenceSum0O(n^3)简单优化过的算法maxSubSequenceSum1O(n^2)分治法优化的算法maxSubSequenceSum2O(n*log(n))动态规划的算法maxSubSequenceSum3O(n)#include#include"mymath.h"/**计算序列的某段子序列的和，maxSubSequenceSum0

2、使用*/staticintsubSequenceSum(inta[],intleft,intright){   inti,sum=0;   for(i=left;i<=right;i++)   {       sum=sum+a[i];   }   returnsum;}/**三层遍历求子序列和的最大值，算法复杂度O(n^3)*/intmaxSubSequenceSum0(inta[],intlen){   inti,j;   intcurSum;/*当前序列和*/   intmaxSum;/*最大序列和*/   /*初始化

3、最大子序列和为序列第一个元素*/   maxSum=a[0];   /*第一层循环定义子序列起始位置*/   for(i=0;i

4、       /*与最大子序列和比较，更新最大子序列和*/           if(curSum>maxSum)           {               maxSum=curSum;           }       }   }   returnmaxSum;}/**双层遍历求子序列和的最大值，算法复杂度O(n^2)*/intmaxSubSequenceSum1(inta[],intlen){   inti,j;   intcurSum;/*当前序列和*/   intmaxSum;/*最大序列和*/   /*

5、初始化最大子序列和为序列第一个元素*/   maxSum=a[0];   /*外层循环定义子序列起始位置*/   for(i=0;i

6、子序列和比较，更新最大子序列和*/           if(curSum>maxSum)           {               maxSum=curSum;           }       }   }   returnmaxSum;}/**某段字序列中，含左边界元素的字序列和中的最大值，_maxSubSequenceSum2中使用*/staticint_maxLeftBoderSubSequenceSum(inta[],intleft,intright){   inti;   intsum=0;   in

7、tmaxSum=a[left];   for(i=left;i<=right;i++)   {       sum+=a[i];       if(sum>maxSum)       {           maxSum=sum;       }   }   returnmaxSum;}/**某段字序列中，含右边界元素的字序列和中的最大值，_maxSubSequenceSum2中使用*/staticint_maxRightBoderSubSequenceSum(inta[],intleft,intright){   inti

8、;   intsum=0;   intmaxSum=a[right];   for(i=right;i>=left;i--)   {       sum+=a[i];       if(sum>maxSum)       {           maxSum=sum;       }