《最大连续子序列之和优秀PPT.ppt》由会员分享，可在线阅读，更多相关《最大连续子序列之和优秀PPT.ppt（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、最大连续子序列之和最大连续子序列之和Csd1006 Csd1006 周建文周建文给出N个个整数A1,A2,AN找出找出该序列的子序列之和的最大值假如全部整数为负,最大值为0(空子序列值为0)算法一o(n*n*n)public int maxSum(inta)int maxSum=0;for(int i=0;ia.length;i+)for(int j=i;ja.length;j+)int thisSum=0;for(int k=I;kmaxSum)maxSum=thisSum;return maxSum;假设我们计算了i到j-1子序列的值,则我们只需额外加一个项,就可以计算从i到j子序列算法二
2、o(n*n)public int maxSum(inta)int maxSum=0;for(int i=0;ia.length;i+)int thisSum=0;for(int j=i;jmaxSum)maxSum=thisSum;Return maxSum;与最大子序列相邻的序列之和确定是负数8,-9,3,5,-7,12算法三o(n)public int maxSum(inta)int maxSum=0;int thisSum=0;for(int i=0,j=0;jmaxSum)maxSum=thisSum;else if(thisSum0)i=j+1;thisSum=0;return maxSum;