专栏首页用户2442861的专栏最大的子序列和问题

最大的子序列和问题

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 条评论
登录 后参与评论

相关文章

  • #define和typedef的用法与区别及面试问题

    在C/C++语言中,typedef常用来定义一个标识符及关键字的别名,它是语言编译过程的一部分,但它并不实际分配内存空间,实例像:

    bear_fish
  • Java的NIO之ByteBuffer底层分析

    类ByteBuffer是Java nio程序经常会用到的类,也是重要类 ,我们通过源码分析该类的实现原理。

    bear_fish
  • CTPN docker/nvidia-docker 安装

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

    bear_fish
  • 算法——(转)动态规划入门

    动态规划相信大家都知道,动态规划算法也是新手在刚接触算法设计时很苦恼的问题,有时候觉得难以理解,但是真正理解之后,就会觉得动态规划其实并没有想象中那么难。网上也...

    mukekeheart
  • 全排列(含递归和非递归的解法)

    全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的。 用C++写一个函数, 如 Foo(const char *str), 打印出 s...

    CloudDeveloper
  • HDU 2084 数塔(简单DP入门)

    数塔 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

    Angel_Kitty
  • 2018-08-22

    JavaEdge
  • 全排列(含递归和非递归的解法)

    全排列在近几年各大网络公司的笔试中出现的比较频繁 首先来看看题目是如何要求的(百度迅雷校招笔试题)。 用C++写一个函数, 如 Foo(const char *...

    范蠡
  • 八数码问题高效算法-HDU 1043

    八数码问题是bfs中的经典问题,经常也会遇到与其相似的题目。用到的思想是bfs+hash;主要是由于状态分散,无法直接用一个确定的数表示。所以导致bfs...

    ACM算法日常
  • cctype

    在头文件<ctype.h>中定义了一些测试字符的函数。在这些函数中,每个函数的参数都是整型int,而每个参数的值或者为EOF,或者为char类型的字符。<cty...

    猿人谷

扫码关注云+社区

领取腾讯云代金券