读书笔记：数组最大子序列问题 及 联机算法

  * Liner-time max imum contiguous subsequence sum algorithm
  * 该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，他就不需要在被存储，
  * 所以，当数组在磁盘或通过互联网传送时，就可以按照顺序读入，在内存中不被储存数组的任何部分，。而且在任何时刻该算法都可以
  * 对已经读入的数据给予序列问题的正确答案（其他几个不具有这个特征），具有这个特征的算法叫联机算法（on-line algorithm）.
  * 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法


 


package com.datastructures.capt0020;


public class MaxSubSum {


 /**
  * Cubic maximum contiguous subsequence sum algorithm.
  * algorithm time complication: (N*N*N+3N*N+2N)/6
  * */
 public static int getMaxSubSum1(int [] a){
  
  int maxSum = 0;
  for(int i=0; i<a.length; i++){
   for(int j=i; j<a.length; j++){
    int thisSum = 0;
    for(int k=i;k<=j;k++){
     thisSum += a[k];
    }
    if(maxSum<thisSum) maxSum = thisSum;
   }
  }
  //int [] a = {1,1,3,-5,9,-4,3,10};
  return maxSum;
 }
 
 /**
  * Quadratic maximum contiguous subsequence sum algorithm
  * algorithm time complication: O(N*N)
  * {1,1,3,-5,9,-7,-4,3,10,-8,3};
  * */
 public static int getMaxSubSum2(int[] a){
  int maxSum = 0;
  for(int i=0; i<a.length; i++){
   int thisSum = 0;
   for(int j=i; j<a.length; j++){  
    thisSum+=a[j];
    if(thisSum>maxSum) maxSum=thisSum;
   }
  }
  return maxSum;
 }
 
 /**
  *Recursive maximum contiguous subsequence sum algorithm.
  *Finds maximum sum in subarrary spnning a[left..right].
  *Does not attempt to maintain actual best sequence. 
  *algorithm time complication: O(N log N)
  */
 private static int maxSumRec(int[] a, int left, int right){
  if((left==right))//Base case
   if(a[left]>0) return a[left];
   else return 0;
  else if((left+1)==right)				//fixd
   return a[left]>=a[right]?a[left]:a[right];
  int center = (left+right)/2;
  int maxLeftSum=maxSumRec(a,left,center);
  int maxRightSum=maxSumRec(a,center,right);
  
  int maxLeftBorderSum = 0, leftBorderSum=0;
  for(int i=center;i>=left;i--){
   leftBorderSum+=a[i];
   if(leftBorderSum>maxLeftBorderSum)
    maxLeftBorderSum = leftBorderSum;
  }
  int maxRightBorderSum=0, rightBorderSum=0;
  for(int i=center+1;i<=right;i++){
   rightBorderSum+=a[i];
   if(rightBorderSum>maxRightBorderSum)
    maxRightBorderSum=rightBorderSum;
  }
  return maxLeftSum>maxRightSum?(maxLeftSum>(maxLeftBorderSum+maxRightBorderSum)?maxLeftSum:(maxLeftBorderSum+maxRightBorderSum))
          :(maxRightSum>(maxLeftBorderSum+maxRightBorderSum)?maxRightSum:(maxLeftBorderSum+maxRightBorderSum));
 }
 /**
  * Driver for divide-andconquer maximum contiguous
  * subsequence sum algorithm.
  * */
 
 public static int getMaxSubSum3(int [] a){
  return maxSumRec(a,0,a.length-1);
 }
 
 /**
  * Liner-time max imum contiguous subsequence sum algorithm
  * 该算法的一个附带的优点是，它只对数据进行一次扫描，一旦a[i]被读入并被处理，他就不需要在被存储，
  * 所以，当数组在磁盘或通过互联网传送时，就可以按照顺序读入，在内存中不被储存数组的任何部分，。而且在任何时刻该算法都可以
  * 对已经读入的数据给予序列问题的正确答案（其他几个不具有这个特征），具有这个特征的算法叫联机算法（on-line algorithm）.
  * 仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法
  * */
 
 public static int getMaxSubSum4(int [] a){
  int maxSum = 0, thisSum=0;
  for(int j=0; j<a.length;j++){
   thisSum+=a[j];
   if(thisSum>maxSum) maxSum=thisSum;
   else if(thisSum<0) thisSum=0;
  }
  return maxSum;
 }
 
 /**
  * @param args
  */
 public static void main(String[] args) {
  int [] a = {1,1,3,-5,-4,3,3};
  System.out.println((0+a.length-1)/2);
  
  System.out.println(MaxSubSum.getMaxSubSum1(a));
  System.out.println(MaxSubSum.getMaxSubSum2(a));
  System.out.println(MaxSubSum.getMaxSubSum3(a));
  System.out.println(MaxSubSum.getMaxSubSum4(a));
  // TODO Auto-generated method stub


 }


}