【DP】53.最大子数组和

Allenlzcoder

已于 2025-05-29 03:05:43 修改

阅读量202

点赞数 2

CC 4.0 BY-SA版权

分类专栏：力扣Top100 文章标签：算法数据结构动态规划最大子数组和

于 2023-12-05 00:10:36 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/134796866

力扣Top100 专栏收录该内容

100 篇文章

订阅专栏

文章介绍了如何使用动态规划方法求解给定整数数组的最大子数组和问题，通过迭代更新dp数组来找到最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目
经典入门动态规划！！！

Python

版本1

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums) # dp[i]表示以nums[i]结尾的最大子数组和
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
        return max(dp)

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = res > dp[i] ? res : dp[i];
        }
        
        return res;
    }
}