【动态规划】连续子数组的最大和

求解代码

public int FindGreatestSumOfSubArray(int[] array) {
int sum = 0;
int max = array[0];
for(int i=0;i<array.length;i++){
sum= Math.max(array[i],sum+array[i]);

max=Math.max(max, sum);
}

return max;
}

小贴士

这题和前文【动态规划】最长上升子序列（一）有些类似，不同的是本题是连续子数组，常规思路的话我们需要利用dp，dp[i] 代表示以元素 array[i] 为结尾的连续子数组最大和。

不难想到，状态转移方程： dp[i] = Math.max(dp[i-1]+array[i], array[i])

这里我们为了进一步简化动态规划，使用一个变量sum来表示当前连续的子数组和。