Kadane算法

如果往事已成负担，那你需要扔掉过去重新开始

---

53. 最大子数组和
918. 环形子数组的最大和

题目描述

53.给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

918.即为环形版的53.

---

Kadane算法

Kadane算法是一种用于解决最大子数组和问题的动态规划算法。这类问题的目标是在给定数组中找到一个连续的子数组，使其元素之和最大（数组含有负数）。

算法的核心思想是通过迭代数组的每个元素，维护两个变量来跟踪局部最优解和全局最优解。

53.
这里我们需要维护两个变量pre与last，其中pre为已探明数组中的最优解（允许有断带，即不与尾部接壤），而last则为包含末尾元素的最优解。

在每一次迭代时，我们首先要更新last，如果旧的last为负，则直接舍去；若为正，但它仍有使用价值。而pre则不需要做额外操作，只需要在last大于pre时更新即可。

int maxSubArray(vector<int>& nums) {
    int pre = nums[0], last = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        last = last > 0 ? last + nums[i] : nums[i];
        pre = max(pre, last);
    }
    return pre;
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

918.
当数组改为环形后，在53的基础上，我们还需要考虑跨越首尾的情况

我最初的想法是，额外维护一个包含头部元素的最优解的变量，最后将首尾合起来，但这样会面临重复计算的问题，即答案数组的长度大于$n$。

后来想到了取反的方法，即在数组总和一定的情况下，一头一尾的最大和子列对应中间一段最小和子列，而这跟53所求是一样的。

在53的基础上，我们这里有四个变量，pre0与last0计算最大子数组和，pre1与last1计算最小子数组和，sum为数组总和。最后，我们只用返回pre0与sum - pre1中的较大者即可。

这里还有一个注意点，当pre1 == sum时，即最小和的情况会取尽所有的数，但此时我们取反后得到的数组将长度为零，我们不希望得到这个结果。从pre1计算的过程来分析，只有当该数组的所有元素都非正才会导致这种情况，那么此时我们只用考虑pre0即可，让pre0在数组中挑选一个最大的数。

int maxSubarraySumCircular(vector<int>& nums) {
    int pre0 = nums[0], last0 = nums[0];
    int pre1 = nums[0], last1 = nums[0];
    int sum = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        int cur = nums[i];
        sum += cur;
        last0 = last0 > 0 ? last0 + cur : cur;
        pre0 = max(pre0, last0);
        last1 = last1 < 0 ? last1 + cur : cur;
        pre1 = min(pre1, last1);
    }
    if (pre1 == sum) return pre0;
    return max(pre0, sum - pre1);
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

Kadane算法是此类题的最优算法，但在追求最优之外，也介绍一些其他算法。

前缀和 + 单调队列

918.
我们将原数组拷贝一份接在后面，原问题化为在新的长为$2n$的数组寻找长度不超过$n$的最大子数组和。

我们用一个单调队列来维护数组的前缀和$S_{i}$，所求化为$S_{i}-S_{j}$的最大值($j < i \leq j + n$)。单调队列中包含当前位置的前$n$个前缀和的一部分，要求后一元素不小于前一元素，因为我们希望队首元素为前$n$个$S_{i}$中的最小值，而其后存放的更大值是希望队首元素因下标差过界弹出时，我们仍能给出新范围中的最小值。

现在从下标$i=1$开始迭代：

• 对于所有$j < i - n$，从队首弹出$S_{j}$（因为我们不希望长度超过$n$的数组出现）
• 计算$S_{i}$，取队首元素$S_{j}$，计算$S_{i} - S_{j}$，并更新答案
• 更新队列，将队尾所有大于等于$S_{i}$的元素弹出后，将$S_{i}$入队

int maxSubarraySumCircular(vector<int>& nums) {
    int n = nums.size();
    deque<pair<int, int>> q;
    int pre = nums[0], res = nums[0];
    q.push_back({0, pre});
    for (int i = 1; i < 2 * n; i++) {
        while (!q.empty() && q.front().first < i - n) {
            q.pop_front();
        }
        
        pre += nums[i % n]; //计算S_i  %代替拷贝操作
        res = max(res, pre - q.front().second); //更新答案
        
        while (!q.empty() && q.back().second >= pre) {
            q.pop_back();
        }
        q.push_back({i, pre});
    }
    return res;
}

• 时间复杂度：$O(n)$，其中 $n$ 是 nums 的长度。我们遍历 $2n$ 个元素，每个元素最多入队出队一次，因此总的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$，其中$n$是 nums 的长度。

线段树

这个算法的作用和意义远在此题之上，这里仅作介绍。
以下内容来自力扣官方题解：

我们定义一个操作 get(a, l, r) 表示查询 $a$ 序列 $[l,r]$ 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 $[l,r]$，我们取$m=\left\lfloor \frac{l+r}{2} \right\rfloor$，对区间 $[l,m]$ 和 $[m+1,r]$ 分治求解。当递归逐层深入直到区间长度缩小为 $1$ 的时候，递归「开始回升」。这个时候我们考虑如何通过 $[l,m]$ 区间的信息和 $[m+1,r]$ 区间的信息合并成区间 $[l,r]$ 的信息。最关键的两个问题是：

• 我们要维护区间的哪些信息呢？
• 我们如何合并这些信息呢？
  对于一个区间 $[l,r]$，我们可以维护四个量：
• $lSum$ 表示 $[l,r]$ 内以 $l$ 为左端点的最大子段和
• $rSum$ 表示 $[l,r]$ 内以 $r$ 为右端点的最大子段和
• $mSum$ 表示 $[l,r]$ 内的最大子段和
• $iSum$ 表示 $[l,r]$ 的区间和

以下简称 $[l,m]$ 为 $[l,r]$ 的「左子区间」，$[m+1,r]$ 为 $[l,r]$ 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 $[l,r]$ 的信息）？对于长度为 $1$ 的区间 $[i,i]$，四个量的值都和 $nums[i]$ 相等。对于长度大于 $1$ 的区间：

• 首先最好维护的是 $iSum$，区间 $[l,r]$ 的 $iSum$ 就等于「左子区间」的 $iSum$ 加上「右子区间」的 $iSum$。
• 对于 $[l,r]$ 的 $lSum$，存在两种可能，它要么等于「左子区间」的 $lSum$，要么等于「左子区间」的 $iSum$ 加上「右子区间」的 $lSum$，二者取大。
• 对于 $[l,r]$ 的 $rSum$，同理，它要么等于「右子区间」的 $rSum$，要么等于「右子区间」的 $iSum$ 加上「左子区间」的 $rSum$，二者取大。
• 当计算好上面的三个量之后，就很好计算 $[l,r]$ 的 $mSum$ 了。我们可以考虑 $[l,r]$ 的 $mSum$ 对应的区间是否跨越 $m$——它可能不跨越 $m$，也就是说 $[l,r]$ 的 $mSum$ 可能是「左子区间」的 $mSum$ 和 「右子区间」的 $mSum$ 中的一个；它也可能跨越 $m$，可能是「左子区间」的 $rSum$ 和 「右子区间」的 $lSum$ 求和。三者取大。
  这样问题就得到了解决。

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};

复杂度分析

假设序列 $a$ 的长度为 $n$。

• 时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为 $O(logn)$，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是 $O(\sum_{i=1}^{\log n}{2^{i-1}})=O(n)$，故渐进时间复杂度为 $O(n)$。
• 空间复杂度：递归会使用 $O(logn)$ 的栈空间，故渐进空间复杂度为 $O(logn)$。

题外话
「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？

对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 $[0,n−1]$，还可以用于解决任意的子区间 $[l,r]$ 的问题。如果我们把 $[0,n−1]$ 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一棵真正的树之后，我们就可以在 $O(logn)$ 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 $O(logn)$ 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。

参考资料：
线段树，从入门到入坑 - 知乎
[力扣53,918] Kadane算法 - 知乎