LeetCode 53. Maximum Subarray (动归)

深碍√TFBOYSˉ_ 2024-04-17 23:16 83阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

(这个送分题，其实就两种情况，你选还是不选，选比不选好就选，不选比选好就不选，我像是在说废话)  
选的情况是相加，不选的情况就是连续中断，值为自己，那么直接和自己比较就ok了  
状态公式如下  
i从1开始的  
dp\[i\] = (dp\[i-1\] + nums\[i-1\]) > nums\[i-1\] ? (dp\[i-1\] + nums\[i-1\]) : nums\[i-1\]

错误示范：我一开始仿佛失了智，不选的时候我理所应当填了个0，dp\[i\] = (dp\[i-1\] + nums\[i-1\]) > 0 ? (dp\[i-1\] + nums\[i-1\]) : 0，结果被case干了：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

我思考了一下，还有负数这一说，而且中断连接至少应该拿起自己吧，然后灰溜溜的改了代码：

class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            //动态规划
            //(这个送分题，其实就两种情况，你选还是不选，选比不选好就选，不选比选好就不选，我像是在说废话)
            //选的情况是相加，不选的情况就是连续中断，值为自己，那么直接和自己比较就ok了
            //状态公式如下
            //i从1开始的
            //dp[i] = (dp[i-1] + nums[i-1]) > nums[i-1] ? (dp[i-1] + nums[i-1]) : nums[i-1]
            int len = nums.size();
            int dp[len + 5];
            int result = -1000000;
            memset(dp, 0, sizeof(dp));
            //只有一个负数的情况
            if(len == 1) return nums[0];
            for(int i = 1; i <= len; i++){
                dp[i] = (dp[i-1] + nums[i-1]) > nums[i-1] ? (dp[i-1] + nums[i-1]) : nums[i-1];
                if(dp[i] > result) result = dp[i];
            }
            return result;
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/89d35729a565418d993486c3a474844b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/55d62d81842c4a14a63723cb1622eb07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/1d9a3cca8d8f4d78b6129e437956ac85.png