java最大子序列

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public class MaxSubSeq {
 5 //    例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。
 6 //    状态转移方程： sum[i]=max(sum[i-1]+a[i],a[i])
 7 // 如果全是负数{ -2, -11, -4, -13, -5, -2 }
 8     
 9     // 获取最大子序列之和
10     public static int getSumOfMaxSubSeq(int[] arr) {
11         int sum = 0;
12         int max = arr[0];
13                 
14         for(int i = 0;  i < arr.length; i++) {
15             sum += arr[i];
16             
17             if (sum > max) {
18                 max = sum;
19             }
20             
21             if (sum < 0) {
22                 sum = 0;
23             }
24         }
25 
26         return max;
27     }
28     
29     // 获取最大子序列
30     public static ArrayList<Integer> getMaxSubSeq(int[] arr) {
31         int sum = 0;
32         int max = arr[0];
33         ArrayList<Integer> list = new ArrayList<Integer>(); // 存储最大子序列
34         ArrayList<Integer> tempList = new ArrayList<Integer>(); // 存储临时序列
35                 
36         for(int i = 0;  i < arr.length; i++) {
37             sum += arr[i];
38             tempList.add(arr[i]);
39             
40             if (sum > max) {
41                 max = sum;
42                 list.clear();
43                 copy(tempList, list);
44             }
45             
46             if (sum < 0) {
47                 sum = 0;
48                 tempList.clear();
49             }
50         }
51 
52         return list;
53     }
54     
55     // 深度copy ArrayList
56     public static void copy(List src,List dest){
57             for (int i = 0 ;i < src.size() ; i++) {
58                 Object obj = src.get(i);            
59                 if (obj instanceof List){
60                     dest.add(new ArrayList());
61                     copy((List)obj,(List)((List)dest).get(i));
62                 }else{
63                     dest.add(obj);
64                 }
65             }
66         }
67       
68     public static void main(String[] args) {
69         int[] arr = { -2, 11, -4, 13, -5, -2 };
70         
71         int max = getSumOfMaxSubSeq(arr);
72         System.out.println("最大子序列之和: " + max);
73         
74         ArrayList<Integer> list = getMaxSubSeq(arr);
75         for(Integer integer: list) {
76             System.out.println("最大子序列: " + integer);
77         }
78     }
79 }