【資料結構和算法分析】最大子序列求和問題及聯機算法

最大子序列求和問題及聯機算法

最大子序列求和：

問題描述：輸入一個整數序列，求出其中連續子序列和的最大值。

算法一：

周遊所有子序列求和，找出其中的最大值

/*
	 * 計算并傳回所最大子序列的和：窮舉周遊   時間複雜度為O(N^3)
	 */
	public int maxSubSum1(int[] a){
		int maxSum = 0;	                            //用來存儲最大子序列的和
		for (int i = 0; i < a.length; i++){     	//i标記子序列的頭	
			for (int j = i; j < a.length; j++){     //j标記子序列的尾				
				int thisSum = 0;                    //用來存儲目前頭尾計算的求和結果			
				for (int k = i; k <= j; k++){    	//将子序列的值依次加入求和結果
					thisSum += a[k];
				}
				if(thisSum > maxSum)	            //存儲兩者的最大值
					maxSum = thisSum;
			}
		}
		return maxSum;
	}
           

算法二：

在算法一的基礎上優化，隻要兩個 for 循環就可以得到所有的子序列

/*
	 * 計算并傳回所最大子序列的和：窮舉優化  時間複雜度為O(N^2)
	 */
	public int maxSubSum2(int[] a){		
		int maxSum = 0;    //用來存儲最大子序列的和
		for (int i = 0; i < a.length; i++){		//i标記子序列的頭
			
			int thisSum = 0;//用來存儲目前頭尾計算的求和結果
			
			for (int j = i; j < a.length; j++){	//j标記子序列的尾
				thisSum += a[j];//将子序列的值加入上次求和結果	
				if(thisSum > maxSum)			//存儲兩者的最大值
					maxSum = thisSum;
			}
		}

		return maxSum;
	}
           

算法三：

分治法：将序列分成左右兩部分，分别求出左，右以及跨越左右的最大子序列和

/*
	 * 分而治之  時間複雜度為O(NlogN)
	 */
	public int maxSubSum3(int[] a,int left,int right){
	
		if(left == right){	//基礎情況：單個元素。直接傳回這個數值或者0
			return a[left];
		}

		int center = (left + right) / 2;      //擷取中點
		
	    int leftMaxSum = maxSubSum3(a,left,center); // 整個出現在輸入資料的左半部的最大子序列求和 
	    
		int rightMaxSum = maxSubSum3(a,center+1,right); // 整個出現在輸入資料的右半部的最大子序列求和 
		
    	int lrMaxSum = max(leftMaxSum,rightMaxSum);  //計算左右兩個子序列求和結果的最大值

		// 橫跨左右兩個部分的最大子序列求和 

		//從center向左處理左半邊
		int maxLeftSum = 0;
		int leftSum = 0;
		for (int i = center; i >= left; i--){
			leftSum += a[i];
			maxLeftSum = max(maxLeftSum,leftSum);
		}

		//從center向右處理右半邊
		int maxRightSum = 0;
		int rightSum = 0;
		for (int j = center+1; j <= right; j++){
			rightSum += a[j];
			maxRightSum = max(maxRightSum,rightSum);
		}

		//傳回求和和前面算出結果的最大值
		return max( lrMaxSum, maxLeftSum+maxRightSum);
	}

    int max(int a,int b){
    	return a>=b ? a:b;
    }
           

算法四：

聯機算法： 隻掃描一遍序列

/*
        * 計算并傳回所最大子序列的和：最優算法  時間複雜度為O(N)
        */
        public int maxSubSum4(int[] a){
    	
    	       int maxSum = 0;     //最終結果
    	       int nowSum = 0;   	//目前求和 

    	        for (int j = 0; j < a.length; j++) {    	//周遊序列的所有元素

    		         nowSum += a[j];    		//将目前元素添加到結果中

    		        if(nowSum > maxSum) {   		//如果大于最大值，則存儲為新的最大值
    		 	         maxSum = nowSum;
    		        }else if(nowSum < 0){
    			         nowSum = 0;
    		        }
    	        }
    	        return maxSum;
        }
           

聯機算法

聯機算法：在任意時刻，算法對要操作的資料隻讀入（掃描）一次，一旦被讀入并處理，它就不需要在被記憶了。而在此處理過程中算法能對它已經讀入的資料立即給出相應子序列問題的正确答案。具有這種特性的算法叫做聯機算法（on-line algorithm）

關于聯機算法的另一道題目，好像是某司的面試題，給定一連串26個字母構成的字元串，判斷哪個字母沒有出現，最好的解法應該還是聯機算法，就是隻周遊一遍，以節省時間上的開銷，比如可以建立一個26個長度的數組，代表26個字母，一旦掃描到某個字母出現了就把标志位更改，最終沒有更改的就是沒有出現的。

問題：想要通過聯機算法來節省時間的開銷，大多要以空間上的開銷來換取，通過額外的空間去記錄一些資料，空間換時間，孰優？具體情況具體分析。