当前位置： 面试刷题>> 环形子数组的最大和(经典算法150题)
### 题目描述
给定一个环形数组（即数组的最后一个元素与第一个元素相连），请编写一个函数来找到该环形数组中所有子数组（包括非环形和环形子数组）的最大和。一个子数组至少包含一个元素，且子数组中的元素必须是连续的。
#### 示例
输入: `[1, -2, 3, -2]`
输出: `3`
解释: 子数组 `[3]` 和 `[1, -2, 3]` 的和都是 3，这是所有子数组中的最大和。
输入: `[5, -3, 5]`
输出: `10`
解释: 子数组 `[5, -3, 5]` 的和是 10，这是所有子数组中的最大和，包括环形子数组。
### 解题思路
为了解决这个问题，我们可以将问题拆分为两部分：
1. **非环形子数组的最大和**：这可以通过Kadane算法（也称为最大子序和算法）来解决。Kadane算法遍历一次数组，记录当前最大子序和以及到当前位置为止的最大子序和。
2. **环形子数组的最大和**：环形子数组的最大和可能跨越数组的两端。为了找到这种子数组，我们可以考虑将原数组“展开”一次（即复制原数组并拼接在末尾），但只考虑从第二个数组开始到原数组结束的部分（因为第一个元素到复制部分的最后一个元素之间的子数组即为原数组的某个子数组，已在第一部分考虑过）。同时，我们需要找到这个“展开”数组中，从第二个元素到最后一个元素之间的最小子序和（因为用总和减去这个最小子序和就能得到可能的最大环形子数组和）。
### PHP 代码示例
```php
function maxSubarraySumCircular($nums) {
$n = count($nums);
if ($n == 0) return 0;
// Kadane算法求非环形最大子数组和
$maxSum = $nums[0];
$currentMax = $nums[0];
for ($i = 1; $i < $n; $i++) {
$currentMax = max($nums[$i], $currentMax + $nums[$i]);
$maxSum = max($maxSum, $currentMax);
}
// 如果所有元素都是负数，则最大和就是单个最大元素
if ($maxSum < 0) return $maxSum;
// 计算环形子数组可能的最大和
$totalSum = array_sum($nums);
$minSum = $nums[0];
$currentMin = $nums[0];
for ($i = 1; $i < $n; $i++) {
$currentMin = min($nums[$i], $currentMin + $nums[$i]);
$minSum = min($minSum, $currentMin);
}
// 环形子数组的最大和可能是总和减去最小子序和
return max($maxSum, $totalSum - $minSum);
}
// 示例
echo maxSubarraySumCircular([1, -2, 3, -2]); // 输出 3
echo maxSubarraySumCircular([5, -3, 5]); // 输出 10
```
### Python 代码示例
```python
def maxSubarraySumCircular(nums):
n = len(nums)
if n == 0:
return 0
# Kadane算法
max_sum = current_max = nums[0]
for num in nums[1:]:
current_max = max(num, current_max + num)
max_sum = max(max_sum, current_max)
if max_sum < 0:
return max_sum
total_sum = sum(nums)
min_sum = current_min = nums[0]
for num in nums[1:]:
current_min = min(num, current_min + num)
min_sum = min(min_sum, current_min)
return max(max_sum, total_sum - min_sum)
# 示例
print(maxSubarraySumCircular([1, -2, 3, -2])) # 输出 3
print(maxSubarraySumCircular([5, -3, 5])) # 输出 10
```
### JavaScript 代码示例
```javascript
function maxSubarraySumCircular(nums) {
const n = nums.length;
if (n === 0) return 0;
// Kadane算法
let maxSum = nums[0];
let currentMax = nums[0];
for (let i = 1; i < n; i++) {
currentMax = Math.max(nums[i], currentMax + nums[i]);
maxSum = Math.max(maxSum, currentMax);
}
if (maxSum < 0) return maxSum;
let totalSum = nums.reduce((a, b) => a + b, 0);
let minSum = nums[0];
let currentMin = nums[0];
for (let i = 1; i < n; i++) {
currentMin = Math.min(nums[i], currentMin + nums[i]);
minSum = Math.min(minSum, currentMin);
}
return Math.max(maxSum, totalSum - minSum);
}
// 示例
console.log(maxSubarraySumCircular([1, -2, 3, -2])); // 输出 3
console.log(maxSubarraySumCircular([5, -3, 5])); // 输出 10
```
这些代码示例展示了如何在PHP、Python和JavaScript中解决环形子数组的最大和问题。