求最大连续子序列的和

本是古典何须时尚 2022-05-31 12:26 204阅读 0赞

给出一个序列，求出最大连续子序列的和，并输出最大连续子序列。

如：\{-10, 1, 2, 3, 4, -5, -23, 100, 3, 7, -21\}，最大子序列是100,3,7,和是110.

public class MaxSubSumDemo {
    
    	public static void main(String[] args) {
    		System.out.println("求最大子序列的和！");
    		maxSubSum();
    	}
    	
    	private static void maxSubSum(){
    		int[] array ={-10, 1, 2, 3, 4, -5, -23, 100, 3, 7, -21};
    			//{-1,0,-2};//{2, 5, -8, 3, 2, -5, 0};//{-2, 11, -4, 13, -5, -2};// {-10, 1, 2, 3, 4, -5, -23,  3, 7,100, -21};//{-10, 1, 2, 3, 4, -5, -23, 100, 3, 7, -21};//
    		int sum =0;
    		int begin =0;
    		int end =0;
    		int finalSum =0;
    		int tempIndex = 0;
    		
    		for(int index =0; index < array.length; index++){
    			if(sum > 0){
    				sum += array[index];				
    			}else{
    				sum = array[index];
    				if(sum > finalSum ){//重新调整子序列的起点
    					begin = index;
    				}
    			}
    			
    			if(sum > finalSum){
    				finalSum = sum;					
    				end = index;//记录子序列的终点
    				tempIndex = begin;//同时记录子序列的起点，方便后面子序列起点大于end时，恢复begin
    			}else if(sum < 0){
    				sum =0;
    				begin = (index+1 < array.length)? index+1:begin;
    			}
    			System.out.println("begin="+begin+",end="+end);
    		}
    		
    		System.out.println("结果：finalSum="+finalSum);
    		
    		begin = (begin > end)? tempIndex:begin;
    		for(int i =begin;i<=end;i++){
    			System.out.println("最大和子序列：array["+i+"] ="+array[i]);
    		}
    	}
    }

运行结果：

求最大子序列的和！
    begin=1,end=0
    begin=1,end=1
    begin=1,end=2
    begin=1,end=3
    begin=1,end=4
    begin=1,end=4
    begin=7,end=4
    begin=7,end=7
    begin=7,end=8
    begin=7,end=9
    begin=7,end=9
    结果：finalSum=110
    最大和子序列：array[7] =100
    最大和子序列：array[8] =3
    最大和子序列：array[9] =7