53-maximum-subarray.md

53. 最大子数组和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解

🚀 打造你的开发者个人IP

掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。

我们向你推荐 Like.dev —— 专为程序员打造的“全能型”个人品牌展示平台。

三位一体（All-In-One）的职场利器：

📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。

🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。

✨ 顶级行业子域名： 提供 name.cto.page、name.engineer.dev 等极具职业含金量的专属域名。

🔗 超酷超短个人主页： 获得极其简练的社交名片，如 is.bio/yourname 或 an.dev/yourname。

立即前往 Like.dev 打造你的个人品牌 →

访问原文链接：53. 最大子数组和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

力扣链接：53. 最大子数组和, 难度等级：中等。

LeetCode “53. 最大子数组和”问题描述

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

子数组是数组中的一个连续部分。

[示例 1]

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 。

[示例 2]

输入: nums = [1]

输出: 1

解释: The subarray [1] has the largest sum 1.

[示例 3]

输入: nums = [5,4,-1,7,8]

输出: 23

解释:

The subarray [5,4,-1,7,8] has the largest sum 23.

[约束]

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

思路 1

本题可以用贪心算法解决（请看方案2），不过这里我们使用另一种方法。
对于nums[i]：
1. 如果上一次的和为负数，我们可以丢弃上一次的和；
2. 如果上一次的和为正数，我们可以将上一次的和加到当前和中。
因此，它符合动态规划问题的特点。

“动态规划”的模式

“动态规划”，需要用dp数组来保存结果。dp[i][j]的值可以由它的前一个（或多个）值通过公式转化出来。因此，dp[i][j]值是一步一步推导出来的，它和先前的dp记录值都有联系。

“动态规划”分为五步

确定数组dp的每个值代表的含义。
初始化数组dp的值。
根据一个示例，按顺序填入dp网格数据。
根据dp网格数据，推导出递推公式。
写出程序，并打印dp数组，不合预期就调整。

细说这五步

确定数组dp的每个值代表的含义。
- 先确定dp是一维数组还是二维数组。“一维滚动数组”意味着每次迭代时都会覆盖数组的值。大多时候，用“一维滚动数组”代替“二维数组”可以简化代码；但有些题目，比如要操作“两个位置可互换的数组”，为了理解方便，还是使用“二维数组”。
- 尝试使用问题所求的返回值的含义作为 dp[i]（一维）或dp[i][j]（二维）的含义，约60%的概率能行。如果不行，再尝试其他含义。
- 设计上尽量考虑保存更丰富的信息，重复信息只在某个dp[i]中保存一次就够了。
- 使用简化的含义。如果用布尔值可以解决问题，就不要用数值。
初始化数组dp的值。dp的值涉及两个层面：
1. dp的长度。通常是：条件数组长度加1或条件数组长度。
2. dp[i]或dp[i][j]的值。dp[0]或dp[0][0]有时需要特殊处理。
根据一个示例，按顺序填入dp网格数据。
- “递推公式”是“动态规划”算法的核心。但“递推公式”是隐晦的，想得到它，就需要制表，用数据启发自己。
- 如果原示例不够好，需要自己重新设计一个。
- 根据示例，填入dp网格数据，需要“按顺序”填，这是很重要的，因为它决定了代码的遍历顺序。
- 大多时候，从左到右，从上到下。但有时需要从右向左、由下而上、从中间向右（或左），如“回文串”问题。有时，还需要一行遍历两次，先正向，再反向。
- 当顺序决定对了，起点就决定好了，从起点出发，“按顺序”填写dp网格数据，这也是在模拟程序处理的过程。
- 在此过程中，您将获得写出“递推公式”的灵感。如果您已经能推导出公式，不需要填完网格。
根据dp网格数据，推导出递推公式。
- 有三个特别的位置需要注意： dp[i - 1][j - 1]、dp[i - 1][j]和dp[i][j - 1]，当前的 dp[i][j]往往取决于它们。
- 操作“两个位置可互换的数组”时，因为对称性，我们可能需要同时使用dp[i - 1][j]和dp[i][j - 1]。
写出程序，并打印dp数组，不合预期就调整。
- 重点分析那些不合预期的数值。

读完了上面的内容，是不是感觉“动态规划”也没有那么难了？试着解出这道题吧。🤗

步骤

动态规划的常用步骤

这五个步骤是解决动态规划问题的模式。

确定dp[i]的含义。
- 假设dp[i]表示索引i处的最大和。这样做行吗？ mark-detail dp[i + 1]无法通过dp[i]计算。所以我们必须改变这个含义。mark-detail
- 该如何设计呢？ mark-detail 如果dp[i]表示索引i处的当前和，dp[i + 1]就可以通过dp[i]计算。最后，我们就可以看到最大和记录在当前和数组中。mark-detail

确定 dp 数组的初值。

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
dp = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

根据一个示例，“按顺序”填入dp网格数据。

nums = [-2,  1, -3,  4, -1,  2,  1, -5,  4]
dp   = [-2,  1,  N,  N,  N,  N,  N,  N,  N] # N 表示现在不关注
dp   = [-2,  1, -2,  N,  N,  N,  N,  N,  N]
dp   = [-2,  1, -2,  4,  N,  N,  N,  N,  N]
dp   = [-2,  1, -2,  4,  3,  N,  N,  N,  N]
dp   = [-2,  1, -2,  4,  3,  5,  N,  N,  N]
dp   = [-2,  1, -2,  4,  3,  5,  6,  N,  N]
dp   = [-2,  1, -2,  4,  3,  5,  6,  1,  N]
dp   = [-2,  1, -2,  4,  3,  5,  6,  1,  5]

根据dp网格数据，推导出“递推公式”。
```
dp[i] = max(nums[i], dp[i - 1] + nums[i])
```
写出程序，并打印dp数组，不合预期就调整。

复杂度

时间复杂度: O(n).
空间复杂度: O(n).

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = nums.copy()

        for i in range(1, len(dp)):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])

        return max(dp)

Java

class Solution {
    public int maxSubArray(int[] nums) {
        var dp = nums.clone();
        
        for (var i = 1; i < dp.length; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }

        return IntStream.of(dp).max().getAsInt(); // if you want to beat 99%, refer to C# soluiton's comment 
    }
}

JavaScript

var maxSubArray = function (nums) {
  const dp = [...nums]

  for (let i = 1; i < dp.length; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
  }

  return Math.max(...dp)
};

Go

func maxSubArray(nums []int) int {
    dp := slices.Clone(nums)

    for i := 1; i < len(nums); i++ {
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
    }

    return slices.Max(dp)
}

Ruby

def max_sub_array(nums)
  dp = nums.clone

  (1...dp.size).each do |i|
    dp[i] = [ nums[i], dp[i - 1] + nums[i] ].max
  end

  dp.max
end

C#

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        var dp = (int[])nums.Clone();

        for (var i = 1; i < dp.Length; i++)
        {
            dp[i] = Math.Max(nums[i], dp[i - 1] + nums[i]);
        }

        return dp.Max(); // if you want to beat 99%, you can use a variable to collect the maximum value: `if (dp[i] > result) result = dp[i];`
    }
}

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        auto dp = nums;

        for (auto i = 1; i < dp.size(); i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
        }

        return *max_element(dp.begin(), dp.end());
    }
};

Other languages

// Welcome to create a PR to complete the code of this language, thanks!

思路 2

本题的“贪心”算法解法和“动态规划”算法解法在本质上是一样的，都是“动态规划”，只不过此处的“贪心”算法把从使用dp一维数组，再降一个维度，变成了只使用两个变量。
此处的“贪心”算法可以被称为“滚动变量”。就像“滚动数组（一维）”对应的是二维数组一样，一滚动就能降一个维度。

复杂度

时间复杂度: O(N).
空间复杂度: O(1).

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = -float('inf')
        pre_sum = 0

        for num in nums:
            pre_sum = max(pre_sum + num, num)
            result = max(result, pre_sum)
        
        return result

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result = INT_MIN;
        int pre_sum = 0;

        for (int num : nums) {
            pre_sum = max(pre_sum + num, num);
            result = max(result, pre_sum);
        }

        return result;
    }
};

Ruby

# @param {Integer[]} nums
# @return {Integer}
def max_sub_array(nums)
  result = -Float::INFINITY
  pre_sum = 0

  nums.each do |num|
    pre_sum = [pre_sum + num, num].max
    result = [result, pre_sum].max
  end

  result
end

Go

func maxSubArray(nums []int) int {
    result := math.MinInt
    preSum := 0

    for _, num := range nums {
        preSum = max(preSum + num, num)
        if preSum > result {
            result = preSum
        }
    }

    return result
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let result = -Infinity;
    let preSum = 0;

    for (const num of nums) {
        preSum = Math.max(preSum + num, num);
        result = Math.max(result, preSum);
    }

    return result;
};

C#

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        int result = int.MinValue;
        int preSum = 0;

        foreach (int num in nums)
        {
            preSum = Math.Max(preSum + num, num);
            result = Math.Max(result, preSum);
        }

        return result;
    }
}

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int result = Integer.MIN_VALUE;
        int preSum = 0;

        for (int num : nums) {
            preSum = Math.max(preSum + num, num);
            result = Math.max(result, preSum);
        }

        return result;
    }
}

Other languages

// Welcome to create a PR to complete the code of this language, thanks!

🚀 打造你的开发者个人IP

掌握算法是成功的基石，而全方位展示你的才华则是获得垂青的关键。

我们向你推荐 Like.dev —— 专为程序员打造的“全能型”个人品牌展示平台。

三位一体（All-In-One）的职场利器：

📄 简历 + 作品集 + 博客： 将你的 GitHub 项目、技术心得与职场经历完美融合。

🌐 永久免费自定义域名： 支持绑定你自己的独立域名，且该功能永久免费。

✨ 顶级行业子域名： 提供 name.cto.page、name.engineer.dev 等极具职业含金量的专属域名。

🔗 超酷超短个人主页： 获得极其简练的社交名片，如 is.bio/yourname 或 an.dev/yourname。

立即前往 Like.dev 打造你的个人品牌 →

访问原文链接：53. 最大子数组和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解，体验更佳！

GitHub 仓库: leetcode-python-java.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

53. 最大子数组和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解

LeetCode “53. 最大子数组和”问题描述

[示例 1]

[示例 2]

[示例 3]

[约束]

思路 1

“动态规划”的模式

“动态规划”分为五步

细说这五步

步骤

动态规划的常用步骤

复杂度

Python

Java

JavaScript

Go

Ruby

C#

C++

Other languages

思路 2

复杂度

Python

C++

Ruby

Go

JavaScript

C#

Java

Other languages

FilesExpand file tree

53-maximum-subarray.md

Latest commit

History

53-maximum-subarray.md

File metadata and controls

53. 最大子数组和 - LeetCode Python/Java/C++/JS/C#/Go/Ruby 题解

LeetCode “53. 最大子数组和”问题描述

[示例 1]

[示例 2]

[示例 3]

[约束]

思路 1

“动态规划”的模式

“动态规划”分为五步

细说这五步

步骤

动态规划的常用步骤

复杂度

Python

Java

JavaScript

Go

Ruby

C#

C++

Other languages

思路 2

复杂度

Python

C++

Ruby

Go

JavaScript

C#

Java

Other languages