《微软面试100题 In Java》03.子数组的最大和

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

分析：首先我们会简单的想到把所有子组数都求出来，但是一个含n个数的数组有n(n+1)/2个子组数，而求和的时间复杂度是O(n),所以这种显然是不行的。

我们都知道当加一个负数时子组数会变小，所以负数是最好别加，但当负数的后一个数大于负数的绝对值那么要保证连续的情况下，这个负数还是有必要加的，于是我们就可以从这一点出发，一步一步求出最大子组数。

Solution 1: Analyze arrays number by number

public class GreatestSum{
	public static int sum(int[] array){
		if(array==null||array.length<=0){
			System.out.println("error") ;
		}
		int n = array.length ;
		int sumTemp = 0 ;
		int sumMax = 0 ;
		
		for(int i=0;i<n;i++){
			sumTemp = sumTemp + array[i] ;
			if(sumTemp<0){
				sumTemp = 0 ;
			}else if(sumTemp>sumMax){
				sumMax = sumTemp ;
			}
		}
		
		return sumMax ;
	}
	public static void main(String[] args){
		int[] array = {1,-2,3,10,-4,7,2,-5} ;
		System.out.println(sum(array)) ;
 	}
}

《微软面试100题 In Java》03.子数组的最大和,布布扣,bubuko.com

《微软面试100题 In Java》03.子数组的最大和

原文：http://blog.csdn.net/speedme/article/details/20777255