力扣-53题最大子序和（C++）- 贪心、动态规划

太过爱你忘了你带给我的痛 2023-01-23 11:59 113阅读 0赞

题目链接：[https://leetcode-cn.com/problems/maximum-subarray/][https_leetcode-cn.com_problems_maximum-subarray]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]  
解一：贪心

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            //思路：贪心
            //1、若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列
            //2、同时，时刻比较当前最大的序列和，用于返回
            int sum_pre=nums[0];
            int max=sum_pre;
            
            if(nums.size()==1) return sum_pre;
    
            for(int i=1;i<nums.size();i++){
        
                if(sum_pre>=0) sum_pre=nums[i]+sum_pre;
                else sum_pre=nums[i];
                
                if(sum_pre>=max) max=sum_pre;
            }
            return max;
        }
    };

解二：动态规划

class Solution {
        
    public:
        int maxSubArray(vector<int>& nums) {
        
            //tip:动态规划
            //1、定义一个函数dp(n)，以第n个数为结束点的子数列的最大和，存在一个递推关系dp(n) = max(dp(n-1) + A[n], A[n]);
            //2、将这些最大和保存下来后，取最大的那个就是，最大子数组和。因为最大连续子数组 等价于 最大的以n个数为结束点的子数列和 附代码
            int n=nums.size();
            int dp[n];
            int result;
    
            result=dp[0]=nums[0];
    
            for(int i=1;i<n;i++){
        
                dp[i]=max(dp[i-1]+nums[i],nums[i]);
                result=max(result,dp[i]);
            }
            return result;
    
            /*
            vector<int> dp(nums.size());
            dp[0]=nums[0];
            for (int i=1;i<dp.size();++i) {
                dp[i]=dp[i-1];
                dp[i]=max(dp[i],dp[i]+nums[i]);
            }
            return dp[nums.size()-1];*/
        }
    };

[https_leetcode-cn.com_problems_maximum-subarray]: https://leetcode-cn.com/problems/maximum-subarray/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20221004/7df95804bef84c60b1191676a1bbff24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20221004/232e48f928634950934f6909004effef.png