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

经典算法——求最大子序列和比较经典的算法问题，能够很好的体现动态规划的实现，以一点“画龙点睛”大大精简了算法复杂度，且实现简单。本文中实现了4种:一般maxSubSequenceSumO0(n"3)简单优化过的算法maxSubSequenceSumlO(n"2)分治法优化的算法maxSubSequenceSum2O(n*log(n))动态规划的算法maxSubSequenceSum3O(n)#include<math.h>#include"mymath.h"/**计算序列的某段子序列的和，maxSubSequenceSumO使用*/staticintsubSequenceSum(inta[],intleft,intright){inti,sum=O;for(i=left;i<=right;i++){sum=sum+a[i];}returnsum;}/**三层遍历求子序列和的最大值，算法复杂度O(n"3)*/intmaxSubSequenceSumO(inta[],intlen){inti,j;intcurSum;/*当前序列和*/intmaxSum;/*最大序列和*//*初始化最大子序列和为序列第一个元素*/maxSum=a[O];/*第一层循环定义子序列起始位置*/for(i=0;i<len;i++){/*起始位置为i，初始化当前和为0*/curSum=0;/*第二层循环定义子序列结束位置*/for(j=i;j<len;j++){/*第三层循环在函数sumSubseqence中，计算子序列和*/curSum=subSequenceSum(a,i,j);/*与最大子序列和比较，更新最大子序列和*/if(curSum>maxSum){maxSum=curSum;}}}returnmaxSum;}/**双层遍历求子序列和的最大值，算法复杂度0(/2)*/intmaxSubSequenceSum1(inta[],intlen){inti,j;intcurSum;/*当前序列和*/intmaxSum;/*最大序列和*//*初始化最大子序列和为序列第一个元素*/maxSum=a[0];/*外层循环定义子序列起始位置*/for(i=0;i<len;i++){/*起始位置为i,初始化当前和为0*/curSum=0;/*内层循环定义子序列结束位置*/for(j=i;j<len;j++){/*计算子序列和，并与最大子序列和比较，更新最大子序列和*/curSum=curSum+a[j];/*与最大子序列和比较，更新最大子序列和*/if(curSum>maxSum){maxSum=curSum;}}}returnmaxSum;}/**某段字序列中，含左边界元素的字序列和中的最大值，_maxSubSequenceSum2中使用*/staticint_maxLeftBoderSubSequenceSum(inta[],intleft,intright){inti;intsum=0;intmaxSum=a[left];for(i=left;i<=right;i++){sum+=a[i];if(sum>maxSum){maxSum=sum;}}returnmaxSum;}/**某段字序列中，含右边界元素的字序列和中的最大值，_maxSubSequenceSum2中使用*/staticint_maxRightBoderSubSequenceSum(inta[],intleft,intright){inti;intsum=0;intmaxSum=a[right];for(i=right;i>=left;i--)sum+=a[i];if(sum>maxSum){maxSum=sum;}}returnmaxSum;}/**求序列某段子序列中子序列和最大值*/staticint_maxSubSequenceSum2(inta[],intleft,intright){intcenter;intleftMaxSum;intrightMaxSum;intmaxLeftBorderSum;intmaxRightBorderSum;/*递归终止条件*/if(left==right){returna[left];}/*分治法递归开始，取中点二分处理*/center=(left+right)>>1;/*center=(left+right)/2;*//*递归求左右子序列段中最大子序列和*/leftMaxSum=_maxSubSequenceSum2(a,left,center);rightMaxSum=_maxSubSequenceSum2(a,center+1,right);maxLeftBorderSum=_maxRightBoderSubSequenceSum(a,left,center);maxRightBorderSum=_maxLeftBoderSubSequenceSum(a,center+1,right);/**二分后的最大值有三个：*1、leftMaxSum，左段最大子序列和*2、rightMaxSum，右段最大子序列和*3、maxLeftBorderSum+maxRightBorderSum，左段最大含右边界子序列和最大值和右段最大含左边界子序列和最大值，二者之和*这三者中的最大值即为分段前的最大子序列和**分治算法核心部分，解决分治后结果归并问题，具体分析：*这是对分段后的子序列的一种划分，有三种，只需分别求出各种的最大值然后在三者之间取一个最大值即可：*1、子序列全在左段，最大子序列和为leftMaxSum*2、子序列全在右段，最大子序列和为rightMaxSum*3、子序列跨左右段，最大字序列和为maxLeftBorderSum+maxRightBorderSum*/returntmax(leftMaxSum,rightMaxSum,maxLeftBorderSum+maxRightBorderSum);}/**分治法实现，算法复杂度O(n*log(n))*分：使用二分法进行分段*治：详细算法见_maxSubSequenceSum2内描述，简述为：*全段最大子序列为以下三者中的最大值*左段最大子序列和*右段最大子序列和*左段最大含右边界子序列和最大值和右段最大含左边界子序列和最大值之和*/intmaxSubSequenceSum2(inta[],intlen){return_maxSubSequenceSum2(a,0,len-1);}/**动态规划实现，算法复杂度O(n)*/intmaxSubSequenceSum3(inta[],intlen){inti;intcurSum;/*当前序列和*/intmaxSum;/*最大序列和*//*初始化当前序列和为0*/curSum=0;/*初始化最大子序列和为序列第一个元素*/maxSum=a[0];/*开始循环求子序列和*/fo