【面试经典 150 | Kadane】环形子数组的最大和

文章目录

写在前面
Tag
题目来源
解题思路
- 方法一：求最大非空子数组和最小子数组和
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【数组】【子数组】

题目来源

918. 环形子数组的最大和

解题思路

在做本题之前需要先完成 53. 最大子数组和。

一个朴素的解法是在数组 nums 尾部接上数组的前 n-1 个元素，然后在新数组中求 最大子数组和。这里只提供思路，不做解答。

接下来学习灵神的思路。

方法一：求最大非空子数组和最小子数组和

思路

首先需要分类讨论：

如果最大子数组没有跨越边界（在 nums 中间）。此时只需要计算最大非空子数组和，即为 maxS。
最大子数组跨越了边界（在 nums 的两端）。由于子数组和 + 其余元素和=sum(nums)，是一个常数，所以其余元素和最小，子数组和越大。于是需要计算 nums 的最小子数组和 minS。
还有一种特殊情况。如果最小数组就是数组 nums 本身，那么跨越边界的最大子数组是空的。

对于特殊情况，如果 minS = sum(nums)，那么最小子数组可以是整个数组。此时直接返回 maxS。

于是：

计算最大非空子数组和 maxS 以及最小子数组和 minS。最小子数组可以是空的，但不能是整个数组。
如果 minS= sum(nums)，返回 maxS；否则返回 max(maxS, sum(nums) - minS)。

代码

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int maxS = INT_MIN; // 最大子数组和，不能为空
        int minS = 0;       // 最小子数组和，可以为空
        int sum = 0, maxTmp = 0, minTmp = 0;
        for (const int& x : nums) {
            maxTmp = max(maxTmp, 0) + x;
            maxS = max(maxS, maxTmp);

            minTmp = min(minTmp, 0) + x;
            minS = min(minS, minTmp);
            
            sum += x;
        }
        return minS == sum ? maxS : max(maxS, sum - minS);
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 是数组 nums 的长度。

空间复杂度： $O (1)$ 。