题目描述[原题链接][https://leetcode-cn.com/problems/maximum-sum-circular-subarray/]
给定一个由整数数组 A
表示的环形数组 C,求 **C**
的非空子数组的最大可能和。
在此处,环形数组意味着数组的末端将会与开头相连呈环状。(形式上,当0 <= i < A.length
时 C[i] = A[i]
,而当 i >= 0
时 C[i+A.length] = C[i]
)
此外,子数组最多只能包含固定缓冲区 A
中的每个元素一次。(形式上,对于子数组 C[i], C[i+1], ..., C[j]
,不存在 i <= k1, k2 <= j
其中 k1 % A.length = k2 % A.length
)
示例 1:
1 | 输入:[1,-2,3,-2] |
示例 2:
1 | 输入:[5,-3,5] |
示例 3:
1 | 输入:[3,-1,2,-1] |
示例 4:
1 | 输入:[3,-2,2,-3] |
示例 5:
1 | 输入:[-2,-3,-1] |
提示:
-30000 <= A[i] <= 30000
1 <= A.length <= 30000
算法描述
首先,我们可以在一个定长数组上完成这个问题。
我们可以认为循环数组 A
的任意子段,一定是定长数组 A+A
的任一个子段。
例如,对于循环数组 A = [0,1,2,3,4,5]
,那么它的子段 [4,5,0,1]
一定也是定长数组 [0,1,2,3,4,5,0,1,2,3,4,5]
的子段。令 B = A + A
就是这个定长数组。
假定 N = A\text{.length}N=A.length,考虑前缀和
P_k = B[0] + B[1] + \cdots + B[k-1]P**k=B[0]+B[1]+⋯+B[k−1]
然后,考虑最大的 P_j - P_iPj−Pi 其中 j - i \leq Nj−i≤N。
考虑第 jj 个候选答案:对于固定 jj 的最优结果 P_j - P_iPj−Pi。我们希望一个 ii 使得 P_iP**i 尽量小 并且满足 j - N \leq i < jj−N≤i<j,称对于第 jj 个候选答案的的最优 ii。我们可以用优先队列实现它。
算法
迭代 jj,每次计算第 jj 个候选答案。我们维护一个 queue
保存可能的最优 ii。
核心想法是如果 i_1 < i_2i1<i2 且 P_{i_1} \geq P_{i_2}P*i1≥P*i2,那么就不再需要考虑 i_1i1。
查看代码了解更多实现细节。
- Java
- Python
C++代码
1 | class Solution { |
Java代码
1 | class Solution { |