剑指 Offer 42 连续子数组的最大和

Tag: 剑指-Offer Posted on 2022-02-26 17:38:22 Edited on 2022-02-26 18:11:50 Views: 154

概述

https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/

https://leetcode.com/problems/maximum-subarray/

题目要求时间复杂度 O(n)。

动态规划法

状态定义:dp[i] 表示从第 i 个字符开始的子数组的最大和。

时间复杂度 O(n^2),成功超时:

class Solution {
public:;
    int maxSubArray(vector<int>& nums) {
        vector<int> dp = nums;
        int ans = dp[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; i --) {
            int sum = nums[i];
            for (int j = i + 1; j < nums.size(); j ++) {
                dp[i] = max(dp[i], sum + dp[j]);
                sum += nums[j];
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

实际上我们完全没必要遍历之后的选择呀,因为之后的选择,必然也是以 nums[i+1] 开头的,所以:

也就是说,这里的选择只有两个:

  1. 不要后一个元素,
  2. 要后一个元素。

时间复杂度降低到 O(n):

class Solution {
public:;
    int maxSubArray(vector<int>& nums) {
        vector<int> dp = nums;
        int ans = dp[nums.size() - 1];
        for (int i = nums.size() - 2; i >= 0; i --) {
            dp[i] = max(dp[i], dp[i] + dp[i+1]);
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

前缀和 + 左右指针

首先构造前缀和数组,之后左右指针逼近。

貌似还得动态规划,就不写了。

分治(求解任意区间的最大子段和)

https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/lian-xu-zi-shu-zu-de-zui-da-he-by-leetco-tiui/

维护 4 个变量:

  1. 以当前区间左端点为起点的最大子段和 lSum,
  2. 以当前区间右端点为终点的最大子段和 rSum,
  3. 当前区间的和 aSum,
  4. 当前区间的最大子段和 mSum。
class Solution {
public:
    struct Sums {
        int lSum, rSum, aSum, mSum;
    };
    int maxSubArray(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1).mSum;
    }

    Sums helper(vector<int>& nums, int l, int r) {
        if (l == r) {
            return {nums[l], nums[l], nums[l], nums[l]};
        }
        int m = (l + r) / 2;
        Sums lSums = helper(nums, l, m);
        Sums rSums = helper(nums, m + 1, r);
        int aSum = lSums.aSum + rSums.aSum;
        int lSum = max(lSums.lSum, lSums.aSum + rSums.lSum);
        int rSum = max(rSums.rSum, rSums.aSum + lSums.rSum);
        int mSum = max(max(lSums.mSum, rSums.mSum), lSums.rSum + rSums.lSum);
        return {lSum, rSum, aSum, mSum};
    }
};

相当于遍历了二叉树中的每一个节点,因此时间复杂度 O(n)。

递归使用 O(logn) 的栈空间,因此空间复杂度 O(logn)。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/