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

目录

• 1️⃣题目描述
• 2️⃣题目解析
• 3️⃣解题代码

1️⃣题目描述

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

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

示例1：

示例2：

示例3：

注意：

• 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;
    }
};

最后就是通过啦！！！

解题代码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;
    }
};

最后同样通过！！！