连续子数组的最大和（Java）

题目：

输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）。

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

最直观的思路：

一个长度为n的数组，总共有n(n + 1) / 2 个子数组；计算出所有子数组的和，即可得到答案，但是其时间复杂度为O(n^2)。不为最优解。

思路：举例分析数组的规律

从上面的实例图去分析的这个例子我们可以总结出如下结论：首先定义两个变量，nCurSum用于存储当前累加子数组的和初始化为0，nGreatestSum用于存取最大的子数组的和初始化为最小的负数。我们遍历这个数组，如果当前nCurSum小于等于0的话（可能为其实时，也可能为中间时），直接将数组当前值赋值给nCurSum，否则将数组当前值加上nCurSum。然后判断nCurSum是否大于nGreatestSum，如果大于则将nCurSum赋值给nGreatestSum，否则进行下次循环，直到循环结束。

代码实现：

boolean g_InvalidInput = false; //新鲜的一招，定义全局布尔变量来区别是错误输入返回0，还是计算后连续子数组的最大的和为0
public int findGreatestSumOfSubArray(int nums[]){
	int lens = nums.length;
	if(nums == null || lens == 0){
		g_InvalidInput = true;
		return 0;
	}
	g_InvalidInput = false;
	int nCurSum = 0;
	int nGreatestSum = 0x80000000;
	for (int i = 0; i < lens; i++) {
		if(nCurSum <= 0){
			nCurSum = nums[i];
		}else{
			nCurSum += nums[i];
		}
		if(nCurSum > nGreatestSum){
			nGreatestSum = nCurSum;
		}
	}
	return nGreatestSum;
}

思路二：应用动态规划

根据题意可知，如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f( i )]，其中0<= i <=n。则我们可以总结出如下递归公式f( i )：

f( i ) = nums[ i ]；在i = 0或者f( i - 1) <= 0；

f( i ) = f( i - 1 ) + nums[ i ]；在i !=0并且f( i - 1 ) > 0；

即：当以第i - 1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果还是比第i个数字本身还要小，所以这种情况下以第i个数字结尾的子数组就是第i个数字本身。如果以第i-1个数字结尾的子数组中所有的数字和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和。

代码实现：

boolean g_InvalidInput = false;
public int findGreatestSumOfSubArray(int nums[]){
	if(nums==null || nums.length == 0){
		g_InvalidInput = true;
		return 0;
	}
	g_InvalidInput = false;
	int nGreatestSum = Integer.MIN_VALUE; //初始化
	int nCurSum = 0;
		
	for(int i = 0; i < nums.length; i++){
		nCurSum = max(nums[i], nGreatestSum + nums[i]);
		nGreatestSum = max(nGreatestSum, nCurSum);
	}	
	return nGreatestSum ;
}
private int max(int num1, int num2) {
	if(num1 > num2){
		return num1;
	}else{
		return num2;
	}
}

小思：

解题思路千千万，Hr在找时间复杂度最优；递归真伟大；递归的for循环实现其实和第一种解法很相似，但是思想不太一样。