LeetCode之最大子段和

原问题

给定一个数组，求这个数组的连续子数组中，最大的那一段的和。
如数组[-2,1,-3,4,-1,2,1,-5,4] 的子段为：[-2,1]、[1,-3,4,-1]、[4,-1,2,1]、…、[-2,1,-3,4,-1,2,1,-5,4]，和最大的是[4,1,2,1]，为6。

子问题

只考虑第一个元素，则最大子段和为其本身 DP[0] = nums[0]
考虑前两个元素，最大子段和为 nums[0],num[1]以及 nums[0] + num[1] 中最大值设为DP[1]
考虑前三个元素，如何求其最大子段和？还是分为两种情况讨论，第三个元素在最后的字串内吗？

若第三个元素也包含在最后的字串内，则DP[2] = Max(DP[1]+nums[2] , nums[2])

确认状态

DP[i] 为以nums[i]结尾的子段的最大最短和，例如 DP[1]则为以nums[1]结尾的最大字段和。

初始状态

dp[0] = nums[0]

dp[1] = max(dp[0]+nums[1] , nums[1])

状态转移方程

dp[i] = max(dp[i-1]+nums[i],nums[i])

代码实现

  public static int maxSubArray(int[] nums) {

        int len = nums.length;

        if (len == 0)

            return 0;

        if (len == 1)

            return nums[0];

        int[] dp = new int[len];

        dp[0] = nums[0];

        int max = dp[0];

        for (int i = 1; i < len; i++) {

            dp[i] = (dp[i - 1] + nums[i] > nums[i]) ? dp[i - 1] + nums[i] : nums[i];

            if (dp[i] > max)

                max = dp[i];

        }

        return max;

    }

巴特西

LeetCode之最大子段和

原问题

子问题

确认状态

初始状态

状态转移方程

代码实现

最新文章

热门文章