【数据结构和算法分析】最大子序列求和问题及联机算法

最大子序列求和问题及联机算法

最大子序列求和：

问题描述：输入一个整数序列，求出其中连续子序列和的最大值。

算法一：

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

/*
	 * 计算并返回所最大子序列的和：穷举遍历   时间复杂度为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个字母，一旦扫描到某个字母出现了就把标志位更改，最终没有更改的就是没有出现的。

问题：想要通过联机算法来节省时间的开销，大多要以空间上的开销来换取，通过额外的空间去记录一些数据，空间换时间，孰优？具体情况具体分析。