DP—子数组,子串系列第一弹 -最大子数组和 -环形子数组的最大和力扣

2024-10-17 07:56:20

你好，欢迎阅读我的文章~

个人主页：@Mike

所属专栏：动态规划

53. 最大子数组和

最大子数组和

分析:

使用动态规划解决

状态表示:

1.以某个位置为结尾

2.以某个位置为起点

这里使用以某个位置为结尾，结合题目要求，定义的状态表示为:

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

dp[i]的所有可能有两种情况

(1).子数组长度为1：此时dp[i]=nums[i];

(2).子数组的长度大于1：此时dp[i]应该等于以i-1为结尾的所有子数组中和的最大值再加上nums[i],也就是dp[i-1]+nums[i]。

因为我们求最大值，所以我们对这两种情况取最大值即可

dp[i]=max(nums[i],dp[i-1]+nums[i]);

代码:

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

            ans=max(ans,dp[i]);
        }

        return ans;
    }
};

动态规划

环形子数组的最大和

分析:

使用动态规划解决

算法思路：

本题与 最大子数组和 的区别在于，考虑问题的时候不仅要分析 数组内的连续区域 ，还要考
虑 数组首尾相连 的一部分。结果的可能情况分为以下两种：

1.结果在数组的内部，包括整个数组。

2.结果在数组首尾相连的一部分上。

对于第一种情况，我们只需按照最大子数组和的方法做即可。

对于第二种情况，我可以换一种思路，既然不在数组的内部的一段，那么我们求出数组的总和，然后在求出数组内的最小子数组和，数组总和减去数组内的最小子数组和就是首尾相连的最大和。

状态表示：

第二种情况：

g[i]表示：以i为结尾的所有子数组中和的最小值。

状态转移方程：

g[i]的所有可能有以下两种情况：

(1).子数组长度为1：此时g[i]=nums[i]

(2).子数组的长度大于1：此时g[i]应该等于以i-1为结尾的所有子数组中和的最小值再加上nums[i]。也就是g[i-1]+nums[i]。

转移方程为:

g[i]=min(nums[i],g[i-1]+nums[i])

代码：

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

        vector<int> maxx(n + 1);
        vector<int> g(n + 1);

        int temp1 = INT_MIN;
        int temp2 = INT_MAX;
        int sum=0;

        for(auto num:nums)
        {
            sum+=num;
        }

        for (int i = 1; i <= n; i++) {
            maxx[i] = max(nums[i - 1], maxx[i - 1] + nums[i - 1]);
            temp1 = max(temp1, maxx[i]);
        }

        for (int i = 1; i <= n; i++) {

            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);
            temp2 = min(temp2, g[i]);
            if(temp2==sum)
            {
                return temp1;
            }
        }

        return max(sum-temp2,temp1);//情况1和情况2取最大值
    }
};

码农公寓