随笔-5  评论-24  文章-0  trackbacks-0
晚自习后半段,写了一道数据结构里的练习题——求最大子序列和。

其实,一般我们解决问题,为了让思路有条理,总会将问题划分,可以是大问题划分成子问题的形式,也可以是对问题所有结果的一些分类,然后一一解决。
由于最近没有使用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 阅读(1977) 评论(1)  编辑 收藏 引用 所属分类: Datastructure and Algorithm

评论:
# re: 最大子序列和问题的3种算法 2010-11-15 10:46 | 护肤品推荐
不明白,看来还是有待提高啊!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理