C/C++教程

DP-LeetCode-3. 最大子序和

本文主要是介绍DP-LeetCode-3. 最大子序和，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路代码

状态表示
当前位置为i，last表示[0, i-1]的最大子序和
now表示[0, i]的最大子序和，如果想让当前的now更大，那么last需要>=0

状态计算
now = max(0, last) + nums[i]
状态计算

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int last = 0;
        int ans = INT_MIN;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int now = max(last, 0) + nums[i];
            ans = max(ans, now);
            last = now;
        }
        return ans;
    }
};
这篇关于DP-LeetCode-3. 最大子序和的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航