AlgoViz Lab交互式算法学习Algorithms first
环形子数组的最大和 · 交互式算法学习
找到环形数组中非空子数组的最大和。
#918 · Kadane 算法
环形子数组的最大和
Maximum Sum Circular Subarray
nums = [5,-3,5]线性序列3 个关键状态
步骤 1普通最大子数组和为 7。
maxSum=75
0-3
15
2推荐
总和减最小子数组
时间
O(n)空间 O(1)环形最大段等价于总和减中间的最小连续段；同时计算普通最大段。
1function maxSubarraySumCircular(a) {2 let total = 0,3 maxCur = 0,4 maxSum = -Infinity,5 minCur = 0,6 minSum = Infinity;7 for (const x of a) {8 maxCur = Math.max(x, maxCur + x);9 maxSum = Math.max(maxSum, maxCur);10 minCur = Math.min(x, minCur + x);11 minSum = Math.min(minSum, minCur);12 total += x13 }14 return maxSum < 0 ? maxSum : Math.max(maxSum, total - minSum);15}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public int maxSubarraySumCircular(int[] nums) {3 final int inf = 1 << 30;4 int pmi = 0, pmx = -inf;5 int ans = -inf, s = 0, smi = inf;6 for (int x : nums) {7 s += x;8 ans = Math.max(ans, s - pmi);9 smi = Math.min(smi, s - pmx);10 pmi = Math.min(pmi, s);11 pmx = Math.max(pmx, s);12 }13 return Math.max(ans, s - smi);14 }15}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
环形子数组的最大和 · 解法对比
找到环形数组中非空子数组的最大和。
- 测试用例
nums = [5,-3,5]- 题目分类
- Kadane 算法
- 解法对比
- 2
复制数组枚举长度≤n窗口
把数组复制一遍，从每个起点枚举最多 n 个元素。
- 时间
O(n²)- 空间
O(n)
总和减最小子数组
环形最大段等价于总和减中间的最小连续段；同时计算普通最大段。
- 时间
O(n)- 空间
O(1)