输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个数组。求所拥有子数组的和的最大值。要求时间复杂度为O(n)
我们可以用动态规划的思想来解决这个问题。以函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)]，其中0<=i<=n。我们可用如下递归公式求f(i)：
简单说明一下动态规划的思想：以第i-1个数结尾的最大和是多少，如果f(i-1)为负数，则与pData[i]相加，结果一定小于pData[i]，所以直接取pData[i]，否则加起来得到以第i个数字结尾的子数组的最大和。
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int[] dp = new int[array.length];
dp[0] = array[0];
int max = Integer.MIN_VALUE;
for(int i=1;i<array.length;i++){
if(array[i]+dp[i-1]<array[i])
dp[i] = array[i];
else
dp[i] = array[i] + dp[i-1];
if(dp[i]>max)
max = dp[i];
}
return max;
}
}
原文：https://www.cnblogs.com/MrSaver/p/13070609.html