剑指Offer:面试题31——连续子数组的最大和(java实现)

问题描述 ：

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

思路1：常规解法，不知道怎么描述了。。

代码：

boolean invalidInput = false; public int FindGreatestSumOfSubArray(int[] array) { if(array == null || array.length == 0){ invalidInput = true; return 0; } int currentSum = 0; int greatestSum = 0x80000000; for(int i = 0; i < array.length; i++){ if(currentSum < 0){ currentSum = array[i]; }else{ currentSum += array[i] } if(currentSum > greatestSum){ greatestSum = currentSum; } } return greatestSum; }

思路2：动态规划

如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)],其中0<=i小于n.

递归公式如下：

f(i) = :pData[i] 当 i = 0或者f(i-1)<=0 :f(i-1)+pData[i] 当i不等于0或者f(i-1)>0

第二种解法代码与第一种其实是一样的。

转载于:https://www.cnblogs.com/wenbaoli/p/5655702.html

相关资源：垃圾分类数据集及代码