news 2026/4/23 18:18:27

用100道题拿下你的算法面试（数组篇-12）：最大环形子数组和

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
用100道题拿下你的算法面试（数组篇-12）：最大环形子数组和

一、面试问题

给定一个环形数组 arr[]，求出任意非空子数组的最大和。环形数组允许从数组末尾绕回到数组开头。

注意：子数组可以跨越末尾并从开头继续，形成一个环形片段。

示例 1：

  • 输入：arr [] = [8, -8, 9, -9, 10, -11, 12]
  • 输出：22
  • 解释：环形子数组 [12, 8, -8, 9, -9, 10] 的和最大，为 22。

示例 2：

  • 输入：arr [] = [4, -1, -2, 3]
  • 输出：7
  • 解释：环形子数组 [3, 4] 的和最大，为 7。

示例 3：

  • 输入：arr [] = [5, -2, 3, 4]
  • 输出：12
  • 解释：环形子数组 [3, 4, 5] 的和最大，为 12。

二、【朴素解法】枚举所有可能的子数组 —— 时间复杂度 O (n²)，空间复杂度 O (1)

(一) 解法思路

将每个元素视作子数组的起点，计算从该起点出发所能得到的最大和，其中既包含线性子数组，也包含环形子数组。

(二) 使用6种语言实现

1. C++

#include <iostream> #include <vector> using namespace std; int maxCircularSum(vector<int> &arr) { int n = arr.size(); int res = arr[0]; // 以索引 i 为起点的子数组 for(int i = 0; i < n; i++) { int currSum = 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j = 0; j < n; j++) { // 环形索引 int idx = (i + j) % n; currSum = currSum + arr[idx]; res = max(res, currSum); } } return res; } int main() { vector<int> arr = {8, -8, 9, -9, 10, -11, 12}; cout << maxCircularSum(arr); }

2. C

#include <stdio.h> int maxCircularSum(int arr[], int n) { int res = arr[0]; // 以索引 i 为起点的子数组 for(int i = 0; i < n; i++) { int currSum = 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j = 0; j < n; j++) { // 环形索引 int idx = (i + j) % n; currSum = currSum + arr[idx]; if (currSum > res) { res = currSum; } } } return res; } int main() { int arr[] = {8, -8, 9, -9, 10, -11, 12}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", maxCircularSum(arr, n)); return 0; }

3. Java

class DSA { static int maxCircularSum(int[] arr) { int n = arr.length; int res = arr[0]; // 以索引 i 为起点的子数组 for(int i = 0; i < n; i++) { int currSum = 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j = 0; j < n; j++) { // 环形索引 int idx = (i + j) % n; currSum = currSum + arr[idx]; res = Math.max(res, currSum); } } return res; } public static void main(String[] args) { int[] arr = {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }

4. Python

def maxCircularSum(arr): n = len(arr) res = arr[0] # 以索引 i 为起点的子数组 for i in range(n): currSum = 0 # 遍历以索引 i 为起点的子数组的所有可能终点 for j in range(n): # 环形索引 idx = (i + j) % n currSum += arr[idx] res = max(res, currSum) return res if __name__ == "__main__": arr = [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))

5. C#

using System; class DSA { static int maxCircularSum(int[] arr) { int n = arr.Length; int res = arr[0]; // 以索引 i 为起点的子数组 for(int i = 0; i < n; i++) { int currSum = 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j = 0; j < n; j++) { // 环形索引 int idx = (i + j) % n; currSum = currSum + arr[idx]; res = Math.Max(res, currSum); } } return res; } static void Main() { int[] arr = {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }

6. JavaScript

using System; class GfG { static int maxCircularSum(int[] arr) { int n = arr.Length; int res = arr[0]; // 以索引 i 为起点的子数组 for(int i = 0; i < n; i++) { int currSum = 0; // 遍历以索引 i 为起点的子数组的所有可能终点 for(int j = 0; j < n; j++) { // 环形索引 int idx = (i + j) % n; currSum = currSum + arr[idx]; res = Math.Max(res, currSum); } } return res; } static void Main() { int[] arr = {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }

(三)代码输出和算法复杂度

输出：

22

时间复杂度：O(n^2)

空间复杂度：O(1)

三、【优化解法】利用前缀和与后缀和 —— 时间复杂度 O (n)，空间复杂度 O (n)

(一) 解法思路

在环形数组中，最大子数组和要么是普通最大和（非环形数组的最大子数组和），要么是环形最大和（同时包含数组开头和结尾元素的子数组和）。普通最大和可以通过卡登算法（Kadane's Algorithm）高效求解。

而环形最大和则通过前缀和与后缀和组合的方式计算。

首先，我们计算最大后缀和数组 maxSuffix，其中 maxSuffix[i] 存储从大于等于 i 的任意索引开始的最大后缀和。随后，遍历输入数组，将截止到索引 i 的前缀和与索引 i+1 处的最大后缀和相结合（避免重复统计第 i 个元素），以此计算环形子数组和，并遍历所有 i 取值取最大值。

(二) 使用6种语言实现

1. C++

#include <iostream> #include <vector> using namespace std; int maxCircularSum(vector<int> &arr) { int n = arr.size(); int suffixSum = arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 vector<int> maxSuffix(n + 1, 0); maxSuffix[n - 1] = arr[n - 1]; for(int i = n - 2; i >= 0; i--) { suffixSum = suffixSum + arr[i]; maxSuffix[i] = max(maxSuffix[i + 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum = arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum = arr[0]; int currSum = 0; int prefix = 0; for(int i = 0; i < n; i++) { // 卡登算法（Kadane's algorithm） currSum = max(currSum + arr[i], arr[i]); normalSum = max(normalSum, currSum); // 计算最大环形和 prefix = prefix + arr[i]; circularSum = max(circularSum, prefix + maxSuffix[i+1]); } return max(circularSum, normalSum); } int main() { vector<int> arr = {8, -8, 9, -9, 10, -11, 12}; cout << maxCircularSum(arr); }

2. C

#include <stdio.h> #include <stdlib.h> int maxCircularSum(int arr[], int n) { int suffixSum = arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int* maxSuffix = (int*)malloc((n + 1) * sizeof(int)); maxSuffix[n - 1] = arr[n - 1]; for(int i = n - 2; i >= 0; i--) { suffixSum = suffixSum + arr[i]; if(maxSuffix[i + 1] > suffixSum) maxSuffix[i] = maxSuffix[i + 1]; else maxSuffix[i] = suffixSum; } // circularSum 表示环形子数组的最大和 int circularSum = arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum = arr[0]; int currSum = 0; int prefix = 0; for(int i = 0; i < n; i++) { // 卡登算法（Kadane's Algorithm） currSum = (currSum + arr[i] > arr[i]) ? currSum + arr[i] : arr[i]; normalSum = (normalSum > currSum) ? normalSum : currSum; // 计算最大环形和 prefix = prefix + arr[i]; if(circularSum < prefix + maxSuffix[i + 1]) circularSum = prefix + maxSuffix[i + 1]; } return (circularSum > normalSum) ? circularSum : normalSum; } int main() { int arr[] = {8, -8, 9, -9, 10, -11, 12}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", maxCircularSum(arr, n)); return 0; }

3. Java

import java.util.Arrays; class DSA { static int maxCircularSum(int[] arr) { int n = arr.length; int suffixSum = arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int[] maxSuffix = new int[n + 1]; maxSuffix[n - 1] = arr[n - 1]; for(int i = n - 2; i >= 0; i--) { suffixSum = suffixSum + arr[i]; maxSuffix[i] = Math.max(maxSuffix[i + 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum = arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum = arr[0]; int currSum = 0; int prefix = 0; for(int i = 0; i < n; i++) { // 卡登算法（Kadane's algorithm） currSum = Math.max(currSum + arr[i], arr[i]); normalSum = Math.max(normalSum, currSum); // 计算最大环形和 prefix = prefix + arr[i]; circularSum = Math.max(circularSum, prefix + maxSuffix[i + 1]); } return Math.max(circularSum, normalSum); } public static void main(String[] args) { int[] arr = {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }

4. Python

def maxCircularSum(arr): n = len(arr) suffixSum = arr[n - 1] # maxSuffix 数组用于存储 # 目前为止的最大后缀和 maxSuffix = [0] * (n + 1) maxSuffix[n - 1] = arr[n - 1] for i in range(n - 2, -1, -1): suffixSum += arr[i] maxSuffix[i] = max(maxSuffix[i + 1], suffixSum) # circularSum 表示环形子数组的最大和 circularSum = arr[0] # normalSum 表示 # 数组视为非环形时的最大子数组和 normalSum = arr[0] currSum = 0 prefix = 0 for i in range(n): # 卡登算法（Kadane's algorithm） currSum = max(currSum + arr[i], arr[i]) normalSum = max(normalSum, currSum) # 计算最大环形和 prefix += arr[i] circularSum = max(circularSum, prefix + maxSuffix[i + 1]) return max(circularSum, normalSum) if __name__ == "__main__": arr = [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))

5. C#

using System; class DSA { static int maxCircularSum(int[] arr) { int n = arr.Length; int suffixSum = arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 int[] maxSuffix = new int[n + 1]; maxSuffix[n - 1] = arr[n - 1]; for(int i = n - 2; i >= 0; i--) { suffixSum = suffixSum + arr[i]; maxSuffix[i] = Math.Max(maxSuffix[i + 1], suffixSum); } // circularSum 表示环形子数组的最大和 int circularSum = arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 int normalSum = arr[0]; int currSum = 0; int prefix = 0; for(int i = 0; i < n; i++) { // 卡登算法（Kadane's algorithm） currSum = Math.Max(currSum + arr[i], arr[i]); normalSum = Math.Max(normalSum, currSum); // 计算最大环形和 prefix = prefix + arr[i]; circularSum = Math.Max(circularSum, prefix + maxSuffix[i + 1]); } return Math.Max(circularSum, normalSum); } static void Main() { int[] arr = {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }

6. JavaScript

function maxCircularSum(arr) { let n = arr.length; let suffixSum = arr[n - 1]; // maxSuffix 数组用于存储 // 目前为止的最大后缀和 let maxSuffix = new Array(n + 1).fill(0); maxSuffix[n - 1] = arr[n - 1]; for(let i = n - 2; i >= 0; i--) { suffixSum += arr[i]; maxSuffix[i] = Math.max(maxSuffix[i + 1], suffixSum); } // circularSum 表示环形子数组的最大和 let circularSum = arr[0]; // normalSum 表示 // 数组视为非环形时的最大子数组和 let normalSum = arr[0]; let currSum = 0; let prefix = 0; for(let i = 0; i < n; i++) { // 卡登算法（Kadane's algorithm） currSum = Math.max(currSum + arr[i], arr[i]); normalSum = Math.max(normalSum, currSum); // 计算最大环形和 prefix += arr[i]; circularSum = Math.max(circularSum, prefix + maxSuffix[i + 1]); } return Math.max(circularSum, normalSum); } // 测试代码 const arr = [8, -8, 9, -9, 10, -11, 12]; console.log(maxCircularSum(arr));

(三)代码输出和算法复杂度

输出：

22

时间复杂度：O(n)

空间复杂度：O(n)

四、【最优解法】使用卡登算法（Kadane 算法）—— 时间复杂度 O (n)，空间复杂度 O (1)

(一) 解法思路

这种方法与前一种思路类似，但核心区别在于：我们同样使用卡登算法（Kadane's Algorithm）来计算环形子数组的最大和。

环形子数组的最大和可以定义为：数组的总和 减去 数组中间某一段子数组的和。因此，想要最大化环形子数组的和，就需要最小化中间这段子数组的和。

环形数组最大子数组和 = 数组总和 - 最小子数组和。

如果最小子数组和等于数组总和，则返回普通最大子数组和。因为当数组所有元素均为负数时，环形和会是 0，但正确答案只能是负数。

(二) 使用6种语言实现

1. C++

#include <iostream> #include <vector> using namespace std; int maxCircularSum(vector<int> &arr) { int totalSum = 0; int currMaxSum = 0, currMinSum = 0; int maxSum = arr[0], minSum = arr[0]; for (int i = 0; i < arr.size(); i++) { // 卡登算法求最大子数组和 currMaxSum = max(currMaxSum + arr[i], arr[i]); maxSum = max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum = min(currMinSum + arr[i], arr[i]); minSum = min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum = totalSum + arr[i]; } int normalSum = maxSum; int circularSum = totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if (minSum == totalSum) return normalSum; return max(normalSum, circularSum); } int main() { vector<int> arr = {8, -8, 9, -9, 10, -11, 12}; cout << maxCircularSum(arr); }

2. C

#include <stdio.h> int maxCircularSum(int arr[], int n) { int totalSum = 0; int currMaxSum = 0, currMinSum = 0; int maxSum = arr[0], minSum = arr[0]; for(int i = 0; i < n; i++) { // 卡登算法求最大子数组和 currMaxSum = (currMaxSum + arr[i] > arr[i]) ? currMaxSum + arr[i] : arr[i]; maxSum = (maxSum > currMaxSum) ? maxSum : currMaxSum; // 卡登算法求最小子数组和 currMinSum = (currMinSum + arr[i] < arr[i]) ? currMinSum + arr[i] : arr[i]; minSum = (minSum < currMinSum) ? minSum : currMinSum; // 输入数组所有元素的总和 totalSum += arr[i]; } int normalSum = maxSum; int circularSum = totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum == totalSum) return normalSum; return (normalSum > circularSum) ? normalSum : circularSum; } int main() { int arr[] = {8, -8, 9, -9, 10, -11, 12}; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", maxCircularSum(arr, n)); return 0; }

3. Java

class DSA { static int maxCircularSum(int[] arr) { int totalSum = 0; int currMaxSum = 0, currMinSum = 0; int maxSum = arr[0], minSum = arr[0]; for(int i = 0; i < arr.length; i++) { // 卡登算法求最大子数组和 currMaxSum = Math.max(currMaxSum + arr[i], arr[i]); maxSum = Math.max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum = Math.min(currMinSum + arr[i], arr[i]); minSum = Math.min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum += arr[i]; } int normalSum = maxSum; int circularSum = totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum == totalSum) return normalSum; return Math.max(normalSum, circularSum); } public static void main(String[] args) { int[] arr = {8, -8, 9, -9, 10, -11, 12}; System.out.println(maxCircularSum(arr)); } }

4. Python

def maxCircularSum(arr): totalSum = 0 currMaxSum = 0 currMinSum = 0 maxSum = arr[0] minSum = arr[0] for i in range(len(arr)): # 卡登算法求最大子数组和 currMaxSum = max(currMaxSum + arr[i], arr[i]) maxSum = max(maxSum, currMaxSum) # 卡登算法求最小子数组和 currMinSum = min(currMinSum + arr[i], arr[i]) minSum = min(minSum, currMinSum) # 输入数组所有元素的总和 totalSum += arr[i] normalSum = maxSum circularSum = totalSum - minSum # 如果最小子数组和等于总和 # 则直接返回普通最大子数组和 if minSum == totalSum: return normalSum return max(normalSum, circularSum) if __name__ == "__main__": arr = [8, -8, 9, -9, 10, -11, 12] print(maxCircularSum(arr))

5. C#

using System; class DSA { static int maxCircularSum(int[] arr) { int totalSum = 0; int currMaxSum = 0, currMinSum = 0; int maxSum = arr[0], minSum = arr[0]; for(int i = 0; i < arr.Length; i++) { // 卡登算法求最大子数组和 currMaxSum = Math.Max(currMaxSum + arr[i], arr[i]); maxSum = Math.Max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum = Math.Min(currMinSum + arr[i], arr[i]); minSum = Math.Min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum += arr[i]; } int normalSum = maxSum; int circularSum = totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if(minSum == totalSum) return normalSum; return Math.Max(normalSum, circularSum); } static void Main() { int[] arr = {8, -8, 9, -9, 10, -11, 12}; Console.WriteLine(maxCircularSum(arr)); } }

6. JavaScript

function maxCircularSum(arr) { let totalSum = 0; let currMaxSum = 0, currMinSum = 0; let maxSum = arr[0], minSum = arr[0]; for (let i = 0; i < arr.length; i++) { // 卡登算法求最大子数组和 currMaxSum = Math.max(currMaxSum + arr[i], arr[i]); maxSum = Math.max(maxSum, currMaxSum); // 卡登算法求最小子数组和 currMinSum = Math.min(currMinSum + arr[i], arr[i]); minSum = Math.min(minSum, currMinSum); // 输入数组所有元素的总和 totalSum += arr[i]; } let normalSum = maxSum; let circularSum = totalSum - minSum; // 如果最小子数组和等于总和 // 则直接返回普通最大子数组和 if (minSum === totalSum) return normalSum; return Math.max(normalSum, circularSum); } // 测试代码 const arr = [ 8, -8, 9, -9, 10, -11, 12 ]; console.log(maxCircularSum(arr));

(三)代码输出和算法复杂度

输出：

22

时间复杂度：O(n)

空间复杂度：O(1)

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/18 18:00:43

告别十六进制恐惧：用d2s-editor轻松掌控暗黑破坏神2存档

告别十六进制恐惧&#xff1a;用d2s-editor轻松掌控暗黑破坏神2存档 【免费下载链接】d2s-editor 项目地址: https://gitcode.com/gh_mirrors/d2/d2s-editor 你是否曾经因为暗黑破坏神2存档损坏而痛失心爱的角色&#xff1f;或者想要尝试不同的角色build却不想从头练级…

作者头像 李华
网站建设 2026/4/18 14:36:15

WaveTools终极指南：三招提升《鸣潮》游戏体验的完整解决方案

WaveTools终极指南&#xff1a;三招提升《鸣潮》游戏体验的完整解决方案 【免费下载链接】WaveTools &#x1f9f0;鸣潮工具箱 项目地址: https://gitcode.com/gh_mirrors/wa/WaveTools 你是否在《鸣潮》中因帧率限制无法流畅体验战斗快感&#xff1f;或者每次切换账号都…

作者头像 李华
网站建设 2026/4/18 9:51:21

AI生成专著的秘密武器！实用工具推荐，开启高效写作之旅

研究人员撰写学术专著的困境与AI工具的助力 对很多研究人员来说&#xff0c;撰写学术专著面临的最大挑战&#xff0c;无疑是“有限的精力”与“无尽的需求”之间的矛盾。专著的创作通常需要三到五年&#xff0c;甚至更长的时间&#xff0c;而研究人员日常还得兼顾教学、科研项…

作者头像 李华
网站建设 2026/4/18 14:27:13

Linux 内核社区终结 AI 代码争议：可用但提交者担责，开源圈震荡待解

【导语&#xff1a;过去开源社区对是否使用 AI 存在争论&#xff0c;如今 Linux 内核社区围绕 AI 生成代码的争议落下帷幕&#xff0c;制定了 AI 代码使用规范&#xff0c;这一举措在开源圈引发震荡。】Linux 内核社区终结 AI 代码争论过去两年&#xff0c;开源社区对 AI 的态度…

作者头像 李华