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

在这里插入图片描述

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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来表示当前连续的子数组和。