[数据结构与算法]LeetCode动态规划专题：第五天

最大子序和

动态规划法

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxn = nums[0], n = nums.size(), pre = nums[0];
        for (int i = 1; i < nums.size(); i ++ )
        {
            int cur = max(pre + nums[i], nums[i]);
            maxn = max(cur, maxn);
            pre = cur;
        }
        return maxn;
    }
};

分治法

暂时不会,哈哈哈哈哈
要用到线段树的知识

环形子数组

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int dp = nums[0], sum = nums[0], maxn = nums[0];
        int n = nums.size();

        for (int i = 1; i < n; i ++ )
        {
            sum += nums[i];
            dp = nums[i] + max(dp, 0);
            maxn = max(dp, maxn);
        }

        int minn = 0;
        dp = nums[0];
        for (int i = 1; i < n - 1; i ++ )
        {
            dp = nums[i] + min(dp, 0);
            minn = min(minn, dp);
        }

        return max(sum - minn, maxn);
    }
};