最大子段和问题Java实现

最大子段和问题

一、问题描述
　　给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大。

　　例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4]，子序列是(11，-4,13)，最大子段和是20。

二、解决方法

1、穷举法（初级版）：SimpleAlgorithmOfMaximumIntervalSumLow.java

　　最容易理解，

　　用三重循环，可遍历所有子区间，一个表示起始位置，一个表示终点位置，一个求当前子序列的和
 1 package cn.com.zfc.everyday.test;
 2 
 3 /** 5  * 
 6  * @title SimpleAlgorithmOfMaximumSegmentSumLow
 7  * @describe 最大子段和的简单算法的初级版
 8  * @author 张富昌
 9  * @date 2017年4月9日下午10:45:51
10  */
11 public class SimpleAlgorithmOfMaximumIntervalSumLow {
12     // 最大子段和的首元素在原序列中的位置
13     private static int startIndex;
14     // 最大子段和的尾元素在原序列中的位置
15     private static int endIndex;
16 
17     public static void main(String[] args) {
18         // 原序列
19         int[] array = { -2, 11, -4, 13, -5, -2 };
20         System.out.println("原序列是：");
21         // 输出原序列
22         printSegment(0, array.length - 1, array);
23         // 求最大子段和
24         int maxSum = maxSum(array);
25         System.out.println("最大字段和：" + maxSum);
26         System.out.println("最大子段和的首元素在原序列中的位置：" + startIndex + "，最大子段和的尾元素在原序列中的位置：" + endIndex);
27         System.out.println("最大字段和的子序列式：");
28         // 输出最大子段和序列
29         printSegment(startIndex, endIndex, array);
30     }
31 
32     /**
33      * 
34      * @param array：原序列
35      * @return：最大子段和
36      */
37     private static int maxSum(int[] array) {
38         // 假设最大子段和为 0
39         int maxSum = 0;
40         // 双重 for 循环遍历所有的子序列
41         for (int i = 0; i < array.length; i++) {
42             for (int j = 0; j < array.length; j++) {
43                 // 一个 for 循环求当前子序列的和
44                 int currentSum = 0;
45                 for (int k = i; k <= j; k++) {
46                     currentSum += array[k];
47                 }
48                 if (currentSum > maxSum) {
49                     maxSum = currentSum;
50                     // 最大子段和的首元素在原序列中的位置
51                     startIndex = i;
52                     // 最大子段和的尾元素在原序列中的位置
53                     endIndex = j;
54                 }
55             }
56         }
57         return maxSum;
58     }
59 
60     /**
61      * 输出序列
62      * 
63      * @param start：序列的开始下标
64      * @param end：序列的结束下标
65      * @param array：要输出的序列
66      */
67     private static void printSegment(int start, int end, int[] array) {
68         for (int i = start; i <= end; i++) {
69             System.out.print(array[i] + " ");
70         }
71         System.out.println();
72     }
73 
74 }

2、穷举法（升级版）：SimpleAlgorithmOfMaximumIntervalSumHigh.java

　避免子序列的重复计算

 1 package cn.com.zfc.everyday.test;
 2 
 3 /**
 4  * 
 5  * @title SimpleAlgorithmOfMaximumIntervalSumHigh
 6  * @describe 最大子段和的简单算法的升级版
 7  * @author 张富昌
 8  * @date 2017年4月9日下午11:17:33
 9  */
10 public class SimpleAlgorithmOfMaximumIntervalSumHigh {
11     // 最大子段和的首元素在原序列中的位置
12     private static int startIndex;
13     // 最大子段和的尾元素在原序列中的位置
14     private static int endIndex;
15 
16     public static void main(String[] args) {
17         // 原序列
18         int[] array = { -2, 11, -4, 13, -5, -2 };
19         System.out.println("原序列是：");
20         // 输出原序列
21         printSegment(0, array.length - 1, array);
22         // 求最大子段和
23         int maxSum = maxSum(array);
24         System.out.println("最大字段和：" + maxSum);
25         System.out.println("最大子段和的首元素在原序列中的位置：" + startIndex + "，最大子段和的尾元素在原序列中的位置：" + endIndex);
26         System.out.println("最大字段和的子序列式：");
27         // 输出最大子段和序列
28         printSegment(startIndex, endIndex, array);
29     }
30 
31     /**
32      * 
33      * @param array：原序列
34      * @return：最大子段和
35      */
36     private static int maxSum(int[] array) {
37         // 假设最大子段和为 0
38         int maxSum = 0;
39         // 双重 for 循环遍历所有的子序列
40         for (int i = 0; i < array.length; i++) {
41             // 当前序列的和
42             int currentSum = 0;
43             // 注意 j 的初始值，避免重复计算
44             for (int j = i; j < array.length; j++) {
45                 currentSum += array[j];
46                 if (currentSum > maxSum) {
47                     maxSum = currentSum;
48                     // 最大子段和的首元素在原序列中的位置
49                     startIndex = i;
50                     // 最大子段和的尾元素在原序列中的位置
51                     endIndex = j;
52                 }
53             }
54         }
55         return maxSum;
56     }
57 
58     /**
59      * 输出序列
60      * 
61      * @param start：序列的开始下标
62      * @param end：序列的结束下标
63      * @param array：要输出的序列
64      */
65     private static void printSegment(int start, int end, int[] array) {
66         for (int i = start; i <= end; i++) {
67             System.out.print(array[i] + " ");
68         }
69         System.out.println();
70     }
71 
72 }

3、分治算法：BranchAlgorithmOfMaximumIntervalSum.java

 1 package cn.com.zfc.everyday.test;
 2 
 3 /**
 4  * 
 5  * @title BranchAlgorithmOfMaximumIntervalSum
 6  * @describe 最大子段和的分治算法： 
 7  *                 所有子区间[start, end]只可能有以下三种可能性: 
 8  *                     在[1,n/2]这个区域内 
 9  *                     在[n/2+1,n]这个区域内
10  *                     起点位于[1,n/2],终点位于[n/2+1,n]内 
11  *                 以上三种情形的最大者，即为所求.
12  *           前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理.
13  *           第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出:
14  *           以n/2为终点，往左移动扩张，求出和最大的一个startSum,以n/2+1为起点，往右移动扩张，求出和最大的一个endSum
15  *           startSum + endSum是第三种情况可能的最大值
16  * @author 张富昌
17  * @date 2017年4月9日下午10:46:32
18  */
19 public class BranchAlgorithmOfMaximumIntervalSum {
20 
21     public static void main(String[] args) {
22         // 原序列
23         int[] array = { -2, 11, -4, 13, -5, -2 };
24         System.out.println("原序列是：");
25         // 输出原序列
26         printSegment(0, array.length - 1, array);
27         // 求最大子段和
28         int maxSum = maxSum(array);
29         System.out.println("最大字段和：" + maxSum);
30     }
31 
32     private static int maxSum(int[] array) {
33         return maxSubSum(array, 1, array.length - 1);
34     }
35 
36     private static int maxSubSum(int[] array, int start, int end) {
37         int sum = 0;
38         if (start == end) {
39             sum = array[start] > 0 ? array[end] : 0;
40         } else {
41             int center = (start + end) / 2;
42             // 以n/2为终点，往左移动扩张，求出和最大的一个startSum
43             int startSum = maxSubSum(array, start, center);
44             // 以n/2+1为起点，往右移动扩张，求出和最大的一个endSum
45             int endSum = maxSubSum(array, center + 1, end);
46             int s1 = 0;
47             int starts = 0;
48             // 以n/2为终点，往左移动扩张，求出和最大的一个 startSum
49             for (int i = center; i >= start; i--) {
50                 starts += array[i];
51                 if (starts > s1) {
52                     s1 = starts;
53                 }
54             }
55             int s2 = 0;
56             int ends = 0;
57             // 以n/2+1为起点，往右移动扩张，求出和最大的一个 endSum
58             for (int i = center + 1; i <= end; i++) {
59                 ends += array[i];
60                 if (ends > s2) {
61                     s1 = ends;
62                 }
63             }
64             sum = s1 + s2;
65             if (sum < startSum) {
66                 sum = startSum;
67             }
68             if (sum < endSum) {
69                 sum = endSum;
70             }
71         }
72         return sum;
73     }
74 
75     /**
76      * 输出序列
77      * 
78      * @param start：序列的开始下标
79      * @param end：序列的结束下标
80      * @param array：要输出的序列
81      */
82     private static void printSegment(int start, int end, int[] array) {
83         for (int i = start; i <= end; i++) {
84             System.out.print(array[i] + " ");
85         }
86         System.out.println();
87     }
88 
89 }

4、动态规划算法

 1 package cn.com.zfc.everyday.test;
 2 
 3 /**
 4  * 
 5  * @title DynamicProgrammingOfMaximumIntervalSum
 6  * @describe 最大子段和的动态规划算法
 7  * @author 张富昌
 8  * @date 2017年4月9日下午10:47:00
 9  */
10 public class DynamicProgrammingOfMaximumIntervalSum {
11     public static void main(String[] args) {
12         // 原序列
13         int[] array = { -2, 11, -4, 13, -5, -2 };
14         System.out.println("原序列是：");
15         // 输出原序列
16         printSegment(0, array.length - 1, array);
17         // 求最大子段和
18         int maxSum = maxSum(array);
19         System.out.println("最大字段和：" + maxSum);
20     }
21 
22     /**
23      * 
24      * @param array：原序列
25      * @return：最大子段和
26      */
27     private static int maxSum(int[] array) {
28         int sum = 0;
29         int b = 0;
30         for (int i = 0; i < array.length; i++) {
31             if (b > 0) {
32                 b += array[i];
33             } else {
34                 b = array[i];
35             }
36             if (b > sum) {
37                 sum = b;
38             }
39         }
40         return sum;
41     }
42 
43     /**
44      * 输出序列
45      * 
46      * @param start：序列的开始下标
47      * @param end：序列的结束下标
48      * @param array：要输出的序列
49      */
50     private static void printSegment(int start, int end, int[] array) {
51         for (int i = start; i <= end; i++) {
52             System.out.print(array[i] + " ");
53         }
54         System.out.println();
55     }
56 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zfc-java/p/6687442.html