首页 > 代码库 > 最大子数组问题(求连续子数组的最大和)
最大子数组问题(求连续子数组的最大和)
在<算法导论>第四章分治策略(Divider and Conquer)4.1节提出了最大子数组问题。其转化就是求数组a={1, -2, 3, 10, -4, 7 , 2, -5}中连续子数组的最大和。
对于这个问题，很容想到一种暴力求解的方法：简单地尝试对所有可能的的组合进行求和。对数组为n存在n*(n-1)/2中组合，然后对每个组合进行求和。即三个for循环遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。记Sum[i,...,j]为数组a中第i个元素到第j个元素的和(其中0<=i<=j<n)，遍历所有可能的Sum[i,...,j],那么时间复杂度(最大运行时间running Time)为Ο(n^3)。
1 package algorithms; 2 3 /** 4 * @author public 5 *本段代码参考编程之美 6 */ 7 public class MaxSubarraySum { 8 9 static int[] a = {1, -2, 3, 10, -4, 7, 2, -5};10 static int sum;11 static int maxSum = 0;12 public static void main(String[] args) {13 // TODO Auto-generated method stub14 for (int i = 0; i < a.length; i++) {15 for (int j = i; j < a.length; j++) {16 for (int k = i; k <= j; k++) {17 sum += a[k];18 }19 if (sum > maxSum) {20 maxSum = sum; 21 }22 sum = 0;//无论是sum>maxSum还是sum<=maxSum都要对sum进行清零操作23 }24 }25 26 System.out.println("maxSum="+maxSum);27 28 }29 30 }
运行结果：
maxSum=18
在算法导论4.1-5习题提到如下思想：最大字数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始，由左到右处理，记录到目前为止已经处理过的最大字数组。若已知a[1,...,j]的最大子数组，基于如下性质将解扩展为a[1,...,j+1]的最大子数组：a[1,...,j+1]的最大子数组要么是a[1,...,j]的最大子数组，要么是某个子数组a[i,...,j+1](1≤i≤j+1)。在已知a[1,...,j]的最大子数组的情况下，可以在线性时间内找出形如a[i,...,j+1]的最大子数组。
实现方法：
1 package algorithms; 2 3 public class FindMaxSubarray { 4 5 static int[] array = {1, -2, 3, 10, -4, 7, 2, -5}; 6 7 public static void main(String[] args) { 8 MaxSum(array); 9 }10 11 private static void MaxSum(int[] arraytmp) {12 // TODO Auto-generated method stub13 if (arraytmp==null) {14 return;15 }16 17 int curSum = 0, maxSum = 0;18 19 int indexStart = 0, indexEnd = 0; //初始化字数组最大和下标20 21 for (int j = 0; j < arraytmp.length; j++) {22 curSum += arraytmp[j];//累加23 24 if (curSum < 0) { //当前和小于0，重置为025 curSum = 0;26 indexStart = j+1;//调整字数组最大和的开始下标27 }28 29 if (curSum > maxSum) { //当前和大于最大和，则重置最大和30 maxSum = curSum;31 indexEnd = j; //调整字数组最大和的结束下标32 }33 34 }35 36 if (maxSum == 0) { //最大和依然为0，说明数组中所有元素都为负值37 maxSum = arraytmp[0];38 indexStart = indexEnd = 0; //初始化子数组最大和下标39 for (int j = 0; j < arraytmp.length; j++) {40 if (arraytmp[j] > maxSum) {41 maxSum =arraytmp[j];42 indexEnd = indexStart = j;//调整子数组最大和下标43 }44 }45 }46 47 for (int i = indexStart; i <= indexEnd; i++) {48 System.out.print(arraytmp[i]+" ");//输出最大和的子数组49 }50 System.out.println();51 System.out.println("maxSum="+maxSum);//输出子数组最大和52 }53 54 }
运行结果：
3 10 -4 7 2 maxSum=18
最大子数组问题(求连续子数组的最大和)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。