求解最大子序列和问题

原题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大；

不想说明什么，我们数据结构老师第一节课就给我们讲这个，以前给实现过一个暴力算法版的算法复杂度O(n2)，现在实现一个动态规划版的；

  

	/* *
         * 求解最大子序列和问题O(n)算法;
	 * @param array
	 */
	public static void maxSubSum(int[] array){  
        
        // 只遍历一遍;  
        int curSum = 0; 		// 当前和;  
        int maxSum = 0;			// 最大和;  
        int start = 0;			// 起始;  
        int end = 0;			// 终止;  
        int testStart = 0; 		// 测试的开始序列;
        
        for(int i = 0; i < array.length; i++){  
            curSum += array[i];  
            if(curSum > maxSum){  
            	start = testStart;
                end = i;  
                maxSum = curSum;  
                
            }else if(curSum < 0){  
                testStart = i + 1;  
                curSum = 0;  
                
            }  
        }  
        
        System.out.println("最大自序列和是："+maxSum);
        System.out.println("start:" + start + ", end: " + end);
        System.out.print("自序列是："); 
        
        for(int i = start; i <= end; i++){  
            System.out.print(array[i] + " ");  
        }  
        
        System.out.println();  
    }

 

 

其基本思想就是拥有最大自序列和的数组不可能是以负数开始的，所以如果当前和小于0，那么字数组必定向前推进1,而其他情况下不会改变最大和和起始终止位置。比起暴力版的这个好啊算法复杂度为O(n)。

<!--EndFragment-->

评论

3 楼 luliangy 2012-12-26  

多谢指正，当时写代码的时候没注意测试

2 楼 flyfox1982 2012-12-24  

//只遍历一遍;
int curSum=0;//当前和;
int maxSum=0;//最大和;
int start=0;//起始;
int end=0;//终止;
int testStart = 0;
for(int i=0;i<array.length;i++){
curSum+=array[i];
if(curSum>maxSum){
end=i;
maxSum=curSum;
start = testStart;
}else if(curSum<0){
testStart=i+1;
curSum=0;
}
}
System.out.println("最大自序列和是："+maxSum);
System.out.println(start + " " + end);
System.out.print("自序列是：");
for(int i=start;i<=end;i++){
System.out.print(array[i]+" ");
}

加了个testStart， 遇到curSum < 0 并不代表，最大和一定在后面，只有再次遇到curSum > maxSum 的时候，把testStart 赋值给start。

1 楼 flyfox1982 2012-12-24  

不对吧：
maxSubSum(new int[]{2,-1,2,3,4,-20,5});

最大自序列和是：10
自序列是：