【剑指offer】连续子数组的最大和
连续子数组的最大和
http://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
max = Math.max(max, array[i]);
}
return max;
}
