java 动态规划解决最大连续子数列和

很多动态规划算法非常像数学中的递推。我们如果能找到一个合适的递推公式，就能很容易的解决问题。
我们用dp[n]表示以第n个数结尾的最大连续子序列的和，这里第n个数必须在子序列中。于是存在以下递推公式：

dp[n] = max(0, dp[n-1]) + num[n]

仔细思考后不难发现这个递推公式是正确的，则整个问题的答案是max(dp[m]) | m∈[1, N]。java语言代码如下：

//dp[i] = max{dp[i-1]+num[i],num[i]}

class Solution {

    public static int maxSubArray(int[] nums) {

        if(nums.length==1){

            return nums[0];

        }

        int res = nums[0];

        for(int i = 1;i<nums.length;i++){

            nums[i] = Math.max(nums[i-1]+nums[i], nums[i]);

            if(res<nums[i]){

                res = nums[i];

            }

        }

        return res;

    }

    public static void main(String[] args){

        int[] test = {-2,-1};

        int res = maxSubArray(test);

        System.out.println(res);

    }

}

巴特西

java 动态规划解决最大连续子数列和

最新文章

热门文章