918. Circular Subarray Sum

Quick Review

Max Subarray Sum 👈这是非常经典的Bottom Up动态规划问题

可用Kadane算法 时间O(n) 空间O(1)

Geeks for Geeks解說Kadane算法

☝️若还不熟悉Kadane算法 看这篇文章

拿捏好第53道题 那就来更奇葩的第918道题吧

Circular Subarray Sum

第53号题只接受我们在长度$n$的数组$nums$中

找到两个索引$i$和$j$ 满足$0 \leq i \leq j < n$

最大化$\text{sum}(nums[i: j + 1])$

918号也和53号题一样接受上述这类子数组

但是918号题另外接受 环形子数组：

找到两个索引$i$和$j$ 满足$0 \leq i \leq j < n$

最大化$\text{sum}(nums[:i] + nums[j: ])$

简而言之便是在$nums$搞 一段Prefix 和 一段Suffix

前提是 不能有任一元素被重复使用

天真的冤枉路🫨

有一说一 我当时拿下第53号题时

本来打算直接搞『阵列拼接模式』

尝试把$nums$拼接成$nums + nums$

好让53号题的精神原封不动套来

结果两个半月连续错了五遍🤣

逆向思考时间😌

又过了快三个月后 某一天我家门口

适逢施工🚧 有挖土机在挖土🪏

看挖土机往地下掏的动作 我恍然大悟：

918号这题要用 『挖除』 才行啦～～

对 就是从$nums$中找出 最小且总和为负值 的那个子数组

把这最负的子数组从$\text{sum}(nums)$扣掉

来一招 "Addition by subtraction" 排除毒瘤

就是最大化的环形子数组啦😁

本来53号题的Kadane算法是找出最大子数组

我们这儿要找出 最小且总和负值的子数组

加了负号这样子 逆向一波

挖土机可不能随便挖的

好比施工时 要先确保不会挖到水管或电线

挖除最负子数组时 先要确保不会『一丝不挂』

什么意思？想想看 万一$nums$全都不是正数

最负子数组不就是$\text{sum}(nums)$？

这时从$\text{sum}(nums)$扣减 等于弄空的子数组

但是子数组不能为空呀

那该怎么办？ 简单追踪$max(nums)$呀

I. $max(nums) \leq 0$ 意味所有元素都没正向作用

此时选拖后腿幅度最小的那条腿 也就是$max(nums)$

II. 至于$max(nums) > 0$时 我们的答案可能是：

1. 如第53号题那样形状的最大子数组
2. 环形子数组：$\text{sum}(nums)$ - 最负子数组

这俩之一 要取俩者较大的做回传

因此本题要追踪的关键变量如下：

1. maxPosSum：最大的正子数组和
2. minNegSum：最小的负子数组和
3. arrayTotalSum：$\text{sum}(nums)$
4. maxNum：$max(nums)$

大致逻辑其实和第53号题还是一样

C++

#include <vector>
using namespace std;

int computeMaxCircularSubarraySum(vector<int>& nums) { // LeetCode Q.918.
    int arrayTotalSum = 0;
    int maxNum = nums.front();

    int posSubarraySum = 0, maxPosSum = 0;

    int negSubarraySum = 0, minNegSum = 0;

    for (const auto& num : nums) {
        if (num > maxNum)
            maxNum = num;

        arrayTotalSum += num;

        posSubarraySum += num;
        if (posSubarraySum > maxPosSum)
            maxPosSum = posSubarraySum;

        if (posSubarraySum <= 0) // Positive sum <= 0: reset subarray.
            posSubarraySum = 0;

        negSubarraySum += num;
        if (negSubarraySum < minNegSum)
            minNegSum = negSubarraySum;

        if (negSubarraySum >= 0) // Negative sum >= 0: reset subarray.
            negSubarraySum = 0;
    }

    if (maxPosSum == 0) // All numbers are non-positive.
        return maxNum;

    return max(arrayTotalSum - minNegSum, maxPosSum);
}

Python

def compute_max_circular_subarray_sum(nums: list[int]) -> int:  # LeetCode Q.918.
    array_total_sum = 0
    max_num = nums[0]

    pos_subarray_sum, max_pos_sum = 0, 0

    neg_subarray_sum, min_neg_sum = 0, 0

    for num in nums:
        if num > max_num: max_num = num

        array_total_sum += num

        pos_subarray_sum += num
        if pos_subarray_sum > max_pos_sum:
            max_pos_sum = pos_subarray_sum

        if pos_subarray_sum <= 0:  # Positive sum <= 0: reset subarray.
            pos_subarray_sum = 0
        
        neg_subarray_sum += num
        if neg_subarray_sum < min_neg_sum:
            min_neg_sum = neg_subarray_sum

        if neg_subarray_sum >= 0:  # Negative sum >= 0: reset subarray.
            neg_subarray_sum = 0

    if max_num <= 0: return max_num  # All numbers are non-positive.

    return max(array_total_sum - min_neg_sum, max_pos_sum)

换个视角 就能时间$O(n)$和空间$O(1)$吃下一道怪题

不过有时要等老半天才终于换对视角😹