最大的子序列和问题

http://blog.csdn.net/zhutulang/article/details/7505785

参考:数据结构与算法分析——Java语言描述

(美) Mark Allen Weiss

给定整数 A1,A2,……AN  (可能有负数),求这个整数序列的最大子序列和。(原书假定如果所有整数为负数,则最大的子序列的和为0。我们这里去掉了这个假定,算法1和算法2只需要把maxSum初始设为 a[0] 即可,算法3做了些修改)

例如:-2 ,11,-4,13,-5,-2, 答案为 20(从A2--A4)

算法1 :

算法1是一种比较容易想到的方法。我们可以这样想,这个子序列可能从第1个元素开始,也有可能从第2、第3、……个元素开始。我们初始假设最大的子序列和 maxSum 是第一个元素。然后分别从第1、第2、………个元素开始计算子序列和,并和当前的和 maxSum 比较,如果大于 maxSum,就将此子序列和赋值给maxSum。

代码如下:

[java] view plaincopy

  1. //算法1
  2. public int maxSubSum1(int []a){  
  3. int thisSum=0,maxSum=a[0];  
  4. for(int i=0;i<a.length;i++)  
  5.         {  
  6.             thisSum=0;  
  7. for(int j=i;j<a.length;j++)  
  8.             {  
  9.                 thisSum+=a[j];  
  10. if(thisSum>maxSum){  
  11.                     maxSum=thisSum;  
  12.                 }  
  13.             }  
  14.         }  
  15. return maxSum;  
  16.     }  

 算法2:

 如图:

我们可以把这个整数数列分成前后两部分。那么最大的子序列和可能出现在三处:前半部分某子序列(设其和为maxLeft),后半部分某子序列(设其和为maxRight),中间部分某子序列(设其和为maxCenter)。前两种情况可以通过递归求解。第三种情况,我们通过分析可知,这种情况下的最大和可以通过求出前半部分的最大和(包含前半部分的最后一个元素)以及后半部分的最大和(包含后半部分的第一个元素)而得到。

代码如下:

[java] view plaincopy

  1. //算法2
  2. public int maxSubSum2(int []a,int left,int right){  
  3. int maxSum=a[0];  
  4. if(left==right){  
  5. if(a[left]>maxSum)  
  6.                 maxSum=a[left];  
  7.           }else{  
  8. int center=(left+right)/2;  
  9. //左半部分最大子序列和
  10. int maxLeft=maxSubSum2(a,left, center);  
  11. //右半部分最大子序列和
  12. int maxRight=maxSubSum2(a, center+1, right);  
  13. //求左半部分包含最后一个元素的最大和
  14. int maxLeftBorder=a[center],leftBorderSum=0;  
  15. for(int i=center;i>=left;i--){  
  16.                   leftBorderSum+=a[i];  
  17. if(leftBorderSum>maxLeftBorder){  
  18.                       maxLeftBorder=leftBorderSum;  
  19.                   }  
  20.               }  
  21. //求右半部分包含第一个元素的最大和
  22. int maxRightBorder=a[center+1],rightBorderSum=0;  
  23. for(int j=center+1;j<=right;j++){  
  24.                   rightBorderSum+=a[j];  
  25. if(rightBorderSum>maxRightBorder){  
  26.                       maxRightBorder=rightBorderSum;  
  27.                   }  
  28.               }  
  29. //横跨前后两部分的最大子序列和
  30. int maxCenter=maxLeftBorder+maxRightBorder;  
  31.               maxSum=Math.max(maxCenter,Math.max(maxLeft, maxRight));  
  32.           }  
  33. return maxSum;  
  34.     }  

算法3:

这种算法效率最高。thisSum每加一个元素后,判断它是否大于 maxSum ,如果大于则 maxSum=thisSum 。判断 thisSum是否小于0,如果小于0,那么说明计算到当前这个位置上的子序列的和是个负数。thisSum=0的效果就相当于把子序列的起始位置推进到当前这个子序列的最后一个位置+1,开始一个新的子序列了。

代码如下:

[java] view plaincopy

  1. //算法3
  2. public int maxSubSum3(int []a){  
  3. int maxSum=a[0],thisSum=0;  
  4. for(int i=0;i<a.length;i++){  
  5.             thisSum+=a[i];  
  6. if(thisSum>maxSum){  
  7.                 maxSum=thisSum;   
  8.             }  
  9. if(thisSum<0){  
  10.                 thisSum=0;  
  11.             }     
  12.         }  
  13. return maxSum;  
  14.     }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

9610
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之旋转数组的最小数字(九度OJ1386)

题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1...

20780
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之旋转数组的最小数字(九度OJ1386)

题目描述: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1...

218100
来自专栏数据结构与算法

1116 四色问题

1116 四色问题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给定N(小于...

29250
来自专栏C语言及其他语言

【每日一题】问题1178:三进制小数

你的任务呢,是将一个有理数转换成三进制小数。“什么是三进制小数呢?”你一定会问,这很明白,就是以三为基(二进制数以2为基,而十进制数则以10为基)的小数。

13330
来自专栏desperate633

LintCode 搜索插入位置题目分析代码

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。 你可以假设在数组中无重复元素。

8520
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

22620
来自专栏Python小屋

奇怪,有的Python函数或方法调用需要两对括号?

本文源自于一位读者的问题:为啥有的函数或方法调用要使用两对括号呢? 但是在我的印象里并没有这种用法啊。于是我简单扫了一眼代码,发现这位朋友说的并不是函数调用需要...

31550
来自专栏企鹅号快讯

Python排序(一)

“为了学习Python编程,通过Python编写了一些算法小程序,作为自己的学习笔记,同时分享给大家共同学习交流!” 现在计算机的广泛使用使得数据无处不在, 而...

22650
来自专栏bboysoul

1493: C语言实验题――圆柱体计算

描述:已知圆柱体的底面半径r和高h,计算圆柱体底面周长和面积、圆柱体侧面积以及圆柱体体积。 输入:输入数据有一行,包括2个正实数r和h,以空格分隔。 输出:...

11810

扫码关注云+社区

领取腾讯云代金券