【DP】LeetCode 53. Maximum Subarray

Allenlzcoder

于 2018-08-02 01:13:37 发布

阅读量316

点赞数

分类专栏： LeetCode练习题文章标签： LeetCode 53. Maximum Subarray

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

版权

LeetCode练习题专栏收录该内容

168 篇文章

订阅专栏

本文介绍了一种使用动态规划解决LeetCode 53题——最大子数组和的方法。通过两个示例展示了如何求解给定整数数组中的连续子数组的最大和，包括初始化状态转移方程及优化迭代过程。

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

LeetCode 53. Maximum Subarray

Solution1：我的答案
动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (!nums.size()) return -1;
        if (nums.size() == 1) return nums[0];
        int dp[n] = {0}, max_sum = INT_MIN;
        dp[0] = nums[0];
        max_sum = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = nums[i] + max(dp[i-1], 0);
            max_sum = max(max_sum, dp[i]);
        }
        return max_sum;
    }
};

优化版：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int temp = nums[0], res = temp;
        for (int i = 1; i < nums.size(); i++) {
            temp = nums[i] + max(temp, 0);
            res = max(res, temp);
        }
        return res;
    }
};