首页 > 代码库 > 求一个数组中最大连续子序列的和
求一个数组中最大连续子序列的和
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 }
求一个数组中最大连续子序列的和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。