【算法|动态规划No.11】leetcode53. 最大子数组和

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

1️⃣题目描述

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

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

示例1：

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

示例2：

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

示例3：

输入：nums = [5,4,-1,7,8]
输出：23

注意：

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

2️⃣题目解析

状态表示：

• dp[i]表示以i位置元素为结尾的所有子数组中的最大和

状态转移方程（分两种情况，以dp[i]的正负为判断条件）：

• 如果dp[i-1] > 0：dp[i] = dp[i-1] + nums[i]
• 否则：dp[i] = nums[i]

3️⃣解题代码

解题代码1：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        vector<int> dp(n);
        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1;i < n;i++)
        {
            if(dp[i-1] > 0)
            {
                dp[i] = dp[i-1] + nums[i];
            }
            else
            {
                dp[i] = nums[i];
            }
            if(dp[i] > max) max = dp[i];
        }
        return max;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

最后就是通过啦！！！

解题代码2：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        int ret = dp[1] = nums[0];
        for(int i = 2;i <= n;i++)
        {
            dp[i] = max((dp[i-1]+nums[i-1]),nums[i-1]);
            ret = max(ret,dp[i]);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

最后同样通过！！！