leetcode 最大子序和动态规划

今天药忘吃喽~ 2023-08-17 15:43 118阅读 0赞

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

> 示例:

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

> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/maximum-subarray][https_leetcode-cn.com_problems_maximum-subarray]

思路：典型的动态规划问题，但是第一次思考错了，第一次是用f\[i\]表示前i个数字组合所能得到的最大值，这样决策方式就是三种，最后发现这种并没有满足连续的条件；正确的应该是f\[i\]表示以第I个数结尾的最大值，这样决策方式只有两种。

错误做法

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if(!nums.size())return 0;
            vector<int> f(nums.size());
            //base case 
            f[0]=nums[0];
            //dp
            for(int j=1;j<nums.size();++j){
                f[j]=max(nums[j],max(f[j-1],f[j-1]+nums[j]));
                cout<<f[j]<<endl;
            }
            return f[nums.size()-1];
        }
    };

正确做法

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            if(!nums.size())return 0;
            //f[i]表示以第i个数结尾的所有连续数组的最大值
            vector<int> f(nums.size());
            //base case 
            f[0]=nums[0];
            //dp
            int ans=f[0];
            for(int i=1;i<nums.size();++i)
                f[i]=max(f[i-1]+nums[i],nums[i]),ans=max(ans,f[i]);
            
            return ans;
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11371370.html

[https_leetcode-cn.com_problems_maximum-subarray]: https://leetcode-cn.com/problems/maximum-subarray