晚自习后半段，写了一道数据结构里的练习题——求最大子序列和。
其实，一般我们解决问题，为了让思路有条理，总会将问题划分，可以是大问题划分成子问题的形式，也可以是对问题所有结果的一些分类，然后一一解决。
由于最近没有使用Java，所以代码用Java实现。
依算法效率递增的顺序，其实亦是人本能思考递减的顺序，分别如下：
1.以子序列起始元素为划分，寻找该起始元素对应的最大子序列和，然后一一比较，得出最大值。
2.用分治的思想，将问题划分为子问题，然后递归地推导到原子项，然后综合。
1 package maxSubSequence;
2
3 public class DivideAndConquer {
4
5 final int length = 8;
6 int[] sequence = new int[length];
7
8 public void initialize(){
9
10 sequence[0]=4;sequence[1]=-3;
11 sequence[2]=5;sequence[3]=-2;
12 sequence[4]=-1;sequence[5]=2;
13 sequence[6]=6;sequence[7]=-2;
14
15 }
16
17 public int compute(){
18 return realCompute(0,sequence.length-1);
19 }
20
21 private int realCompute(int start,int end){
22 if(start == end)
23 return sequence[start];
24 int leftMid = (start+end)/2,rightMid = leftMid+1;
25 int leftMax = realCompute(start,leftMid);
26 int rightMax = realCompute(rightMid,end);
27 int leftBoundryMax = getLeftBoundryMax(start,leftMid);
28 int rightBoundryMax = getRightBoundryMax(rightMid,end);
29
30 return leftMax>rightMax ?
31 leftMax>leftBoundryMax+rightBoundryMax ? leftMax:leftBoundryMax+rightBoundryMax
32 :rightMax>leftBoundryMax+rightBoundryMax ? rightMax:leftBoundryMax+rightBoundryMax;
33 }
34
35 private int getRightBoundryMax(int rightMid, int end) {
36
37 int tmp = 0,max = 0;
38
39 for(int i = rightMid;i<=end;i++){
40 tmp += sequence[i];
41 if(tmp > max)
42 max = tmp;
43 }
44 return max;
45 }
46
47 private int getLeftBoundryMax(int start, int leftMid) {
48
49 int tmp = 0,max = 0;
50
51 for(int i = leftMid;i>=start;i--){
52 tmp += sequence[i];
53 if(tmp > max)
54 max = tmp;
55 }
56 return max;
57 }
58
59 public static void main(String[] args){
60 DivideAndConquer divided = new DivideAndConquer();
61 divided.initialize();
62 int max = divided.compute();
63 System.out.println(max);
64 }
65 }
3.O（N）的联机算法，即完美算法。该算法扫描数据一次，且随时保存已处理的最大值。将每一个即将处理的可能最大项进行试探性处理，而后更新。注意到最大项必然是正项开始这一事实，其实该算法亦是一个划分，只是在已知已处理数据为负的情况下摒弃了算法1中的无效计算。从此观点看，算法的意义便在于让计算机尽量做有效，必要的比较。省去无意义或是重复的计算。
1 package maxSubSequence;
2
3 /**
4 * the central idea of the perfect algorithm to compute the max sub sequence
5 * is always keep the current largest result and use the incoming item to
6 * judge the undertaking "max" subsequence
7 * @author Yj_W
8 *
9 */
10 public class Perfect {
11 final int length = 8;
12 int[] sequence = new int[length];
13
14 public void initialize(){
15
16 sequence[0]=4;sequence[1]=-3;
17 sequence[2]=5;sequence[3]=-2;
18 sequence[4]=-1;sequence[5]=2;
19 sequence[6]=6;sequence[7]=-2;
20
21 }
22
23 public void computeMaxSubSequence(){
24 int max = 0,tmp = 0;
25
26 for(int i=0;i=0)
28 tmp +=sequence[i];
29 else if((tmp += sequence[i]) < 0){
30 tmp = 0;
31 }
32
33 if(tmp>max)
34 max = tmp;
35 }
36 System.out.println(max);
37 }
38
39 public static void main(String[] args){
40 Perfect maxSub = new Perfect();
41 maxSub.initialize();
42 maxSub.computeMaxSubSequence();
43 }
44 }1 package maxSubSequence;
2
3 /**
4 * the central idea of the perfect algorithm to compute the max sub sequence
5 * is always keep the current largest result and use the incoming item to
6 * judge the undertaking "max" subsequence
7 * @author Yj_W
8 *
9 */
10 public class Perfect {
11 final int length = 8;
12 int[] sequence = new int[length];
13
14 public void initialize(){
15
16 sequence[0]=4;sequence[1]=-3;
17 sequence[2]=5;sequence[3]=-2;
18 sequence[4]=-1;sequence[5]=2;
19 sequence[6]=6;sequence[7]=-2;
20
21 }
22
23 public void computeMaxSubSequence(){
24 int max = 0,tmp = 0;
25
26 for(int i=0;i<sequence.length;i++){
27 if(sequence[i]>=0)
28 tmp +=sequence[i];
29 else if((tmp += sequence[i]) < 0){
30 tmp = 0;
31 }
32
33 if(tmp>max)
34 max = tmp;
35 }
36 System.out.println(max);
37 }
38
39 public static void main(String[] args){
40 Perfect maxSub = new Perfect();
41 maxSub.initialize();
42 maxSub.computeMaxSubSequence();
43 }
44 }
posted on 2010-11-15 00:23
yenchieh 阅读(2002)
评论(1) 编辑 收藏 引用 所属分类:
Datastructure and Algorithm