当前位置：
  1. 首页
  2. 五大算法思想
  3. 正文

动归训练二：Leetcode 53. 最大子序和

五大算法思想 0 2.4K

问题描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
Java

示例 2：

输入：nums = [1]
输出：1
Java

示例 3：

输入：nums = [0]
输出：0
Java

示例 4：

输入：nums = [-1]
输出：-1
Java

示例 5：

输入：nums = [-100000]
输出：-100000
Java

提示：

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

原题链接：53. 最大子序和

题解

按照我们说的动态规划三部曲来，没看过的看我之前写的文章：告别动态规划，谈谈我的一些经验

一、定义数组的含义

本题是求找到一个具有最大和的连续子数组，并且子数组必须至少含有一个元素，那么 dp[i] 的含义应该定位为啥呢？

这个其实不是那么好找，需要大家多做一做题，才可以很快着准确判断出来，对于这道题， dp[i] 的含义是以 nums[i] 结尾的子序的最大和。那么我们要找的答案就是

max = max(dp[0], dp[1],….., dp[n-1])。就是看看以哪个 num[i] 结尾的连续子序列和是最大的。

二、找出数组元素之间的关系式

对于每一个 dp[i]，我们必须以 nums[i] 结尾，那么对于 dp[i] 与 dp[i-1] 的关系则为

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

其实这很好理解，假如 dp[i] 是个正数，那我 dp[i] 肯定要你，把你包含进来，假如 dpj[i-1] 是个负数，那么不好意思，你就是个累赘，我 dp[i] 不需要你。

三、找出数组初始值

初始值还是比较容易找的，当只有一个元素的时候

dp[0] = num[0]

所以最终代码如下

public class lc53_MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0)
            return 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;
    }
}
Java

相关训练题

动归训练一：Leetcode 198.大家劫舍

动规训练三：Leetcode 322. 零钱兑换

动规训练四：Leetcode 10. 正则表达式

上一篇 Cookie 和 Session 有什么区别？
下一篇 动规训练三：Leetcode 322. 零钱兑换

发表评论

后才能评论

评论(5)


五大算法思想系列教程