求一个数组中最大连续子序列的和

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

求一个数组中最大连续子序列的和10.求一个数组中最大连续子序列的和参考链接:http://blog.csdn.net/butwang/article/details/4691974

思路:如果已经知道在前0~k-1共k个元素中,在最大和为MaxAll[k-1], 怎么求0~k共k+1个元素的MaxAll[k]。 如果前k个元素的最大和子序列包括a[k-1],则很容易知道MaxAll[k] = max(MaxAll[k-1] + a[k], a[k])。那如果前k个元素的最大和子序列不包括a[k-1]呢?在数组后面增加一个元素,会改变数组最后面子序列的和,因此MaxAll[k] = max(MaxAll[k-1], MaxAll[k-1] + a[k], a[k])。定义EndMax[k-1]为前k个元素中包括a[k-1]的最大子序列和。则递推公式如下:

EndMax[k] = max(EndMax[k-1] + a[k], a[k])

MaxAll[k] = max(MaxAll[k-1], EndMax[k])

可以看出,没有必要使用两个数组,可以使用两个变量取代MaxAll[k]和EndMax[k]。

代码:

1 package algorithm; 2 3 public class maxSubSum { 4 // 求一个数组中最大子序列的和 5 public static void main(String[] args) { 6 int a[] = { -3, 3, -1, 4, -2, -1 }; 7 8 int AllMax = a[0]; 9 int EndMax = a[0];10 11 int AllMaxStart = 0, AllMaxEnd = 0, EndMaxStart = 0, EndMaxEnd = 0;12 13 for (int i = 1; i < a.length; i++) {14 if (EndMax + a[i] > a[i]) {15 EndMax = EndMax + a[i];16 EndMaxEnd = i;17 } else {18 EndMax = a[i];19 EndMaxStart = i;20 EndMaxEnd = i;21 }22 23 if (EndMax > AllMax) {24 AllMax = EndMax;25 AllMaxStart = EndMaxStart;26 AllMaxEnd = EndMaxEnd;27 }28 }29 30 System.out.PRintln("MaxValue: "+AllMax+", Start: "+AllMaxStart+", End: "+AllMaxEnd);31 }32 }

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航