Leetcode|线性序列|53/42. 连续子数组的最大和（暴力+贪心+动态规划包含结尾元素）

SL_World

发布于 2021-09-18 16:44:03

54500

代码可运行

文章被收录于专栏：XX

运行总次数：0

代码可运行

文章目录

1 暴力 + sum小于0剪枝

class Solution { 
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        int maxSum = INT_MIN;
        for (int i = 0; i < size; i++) {
            int sum = 0;
            for (int j = i; j < size; j++) {
                sum += nums[j];
                maxSum = max(maxSum, sum);
                // 和小于0剪枝
                if (sum < 0) break;
            }
        }
        return maxSum;
    }
};

2 区间贪心

时间复杂度：O(n)

局部最优：当前和为负数时立即停止加和，因为前面的负数和只会拉低后面的和（全负数案例）

全局最优：选取最大“连续和”

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        int curSum = 0;  // 当前区间中的和
        for (int i = 0; i < nums.size(); i++) {
            curSum += nums[i];
            maxSum = max(maxSum, curSum);
            // 核心：若之前的curSum为负数, 则置0, 因为前面的负数和一定会拉低后面的正和(全负数也满足)
            curSum = max(curSum, 0);  // 修正最大和的起始位置
        }
        return maxSum;
    }
};

3 动态规划（未状态压缩）

【本题特点】：子数组要保证连续性，由于存在负数，不适合用滑动窗口方法
【解题关键】：dp[i]数组含义要包含结尾元素的默认添加
【选择】：①nums[i]独立成组 or ②加入到i - 1的数组中
【状态转移方程】：dp[i] = max(nums[i], dp[i - 1] + nums[i])

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size + 1, INT_MIN);
        dp[0] = nums[0];    // 方便状态转移方程
        int maxSum = dp[0];
        for (int i = 1; i < size; i++) {
            // 选择(1)nums[i]独立成组 or (2)加入到i - 1的成组元素中
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            maxSum = max(maxSum, dp[i]);
        }
        return maxSum;
    }
};

4 动态规划（状态压缩）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        // preSum需要初始化为nums[0]以便初始状态转移
        int preSum = nums[0], curSum = 0;   
        int maxSum = nums[0];
        for (int i = 1; i < size; i++) {
            // dp[i] = max(nums[i], dp[i - 1] + nums[i])
            curSum = max(nums[i], preSum + nums[i]);
            preSum = curSum;
            maxSum = max(maxSum, curSum);
        }
        return maxSum;
    }
};