leetcode 最大子序和 简单

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

 dp[i][1] 表示以第 i 个元素结尾的最大子序和，dp[i][0] 表示不以 i 结尾的最大子序和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        memset(dp, -0x3f, sizeof(dp));
        for(int i = 0; i < nums.size(); ++ i) {
            if(i == 0) dp[i][1] = nums[i];
            else {
                dp[i][1] = max(dp[i - 1][1] + nums[i], nums[i]);
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
    static const int maxn = 3e4 + 10;
    int dp[maxn][2];
};

然后很明显可以用滚动数组优化，变成空间复杂度O(1)：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        memset(dp, -0x3f, sizeof(dp));
        for(int i = 0; i < nums.size(); ++ i) {
            if(i == 0) dp[i % 2][1] = nums[i];
            else {
                dp[i % 2][1] = max(dp[(i - 1) % 2][1] + nums[i], nums[i]);
                dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]);
            }
        }
        return max(dp[(nums.size() - 1) % 2][0], dp[(nums.size() - 1) % 2][1]);
    }
    static const int maxn = 3e4 + 10;
    int dp[2][2];
};

这篇关于leetcode 最大子序和 简单的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！