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

求解代码

publicintFindGreatestSumOfSubArray(int[]array){intsum=0;intmax=array[0];for(inti=0;i<array.length;i++){sum=Math.max(array[i],sum+array[i]);max=Math.max(max,sum);}returnmax;}

小贴士

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

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

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