当前位置： 面试刷题>> 最大子数组Ⅱ (经典算法题500道)
### 题目描述
**最大子数组 II**
给定一个整数数组 `nums` 和一个整数 `k`，你需要找到该数组中和最大的子数组，但要求子数组中最多只能包含 `k` 个不同的整数。返回这个子数组的最大可能和。
**示例 1**:
```
输入: nums = [1,5,4,2,9,9,9], k = 3
输出: 20
解释: 子数组 [5,4,2,9,9,9] 的和是 29，但是它包含 4 个不同的整数。子数组 [1,5,4,2,9] 的和是 21，但是它包含 5 个不同的整数。子数组 [5,9,9,9] 的和是 23，但是它包含 2 个不同的整数。所以最优解是 [4,2,9,9,9]，和是 20，并且只包含 3 个不同的整数。
```
**示例 2**:
```
输入: nums = [3,9,3], k = 2
输出: 9
解释: 子数组 [9] 的和是 9，包含 1 个不同的整数。
```
**注意**:
1. `1 <= nums.length <= 10^5`
2. `-10^4 <= nums[i] <= 10^4`
3. `1 <= k <= nums.length`
### 解题思路
这个问题可以通过滑动窗口和哈希表结合的方法来解决。我们需要维护一个窗口，窗口内的元素种类不超过 `k` 种，并实时计算窗口内元素的总和。当窗口内的元素种类超过 `k` 时，需要移动窗口的左边界，同时从哈希表中移除对应的元素，直到窗口内的元素种类不超过 `k` 为止。
### PHP 示例代码
```php
function maxSubArraySumWithKDistinct($nums, $k) {
$maxSum = PHP_INT_MIN;
$currentSum = 0;
$left = 0;
$distinctCount = array();
for ($right = 0; $right < count($nums); $right++) {
if (!isset($distinctCount[$nums[$right]])) {
$distinctCount[$nums[$right]] = 1;
} else {
$distinctCount[$nums[$right]]++;
}
$currentSum += $nums[$right];
while (count($distinctCount) > $k) {
$currentSum -= $nums[$left];
$distinctCount[$nums[$left]]--;
if ($distinctCount[$nums[$left]] == 0) {
unset($distinctCount[$nums[$left]]);
}
$left++;
}
$maxSum = max($maxSum, $currentSum);
}
return $maxSum;
}
// 测试
$nums = [1,5,4,2,9,9,9];
$k = 3;
echo maxSubArraySumWithKDistinct($nums, $k); // 输出 20
```
### Python 示例代码
```python
def maxSubArraySumWithKDistinct(nums, k):
max_sum = float('-inf')
current_sum = 0
left = 0
distinct_count = {}
for right in range(len(nums)):
if nums[right] not in distinct_count:
distinct_count[nums[right]] = 0
distinct_count[nums[right]] += 1
current_sum += nums[right]
while len(distinct_count) > k:
current_sum -= nums[left]
distinct_count[nums[left]] -= 1
if distinct_count[nums[left]] == 0:
del distinct_count[nums[left]]
left += 1
max_sum = max(max_sum, current_sum)
return max_sum
# 测试
nums = [1,5,4,2,9,9,9]
k = 3
print(maxSubArraySumWithKDistinct(nums, k)) # 输出 20
```
### JavaScript 示例代码
```javascript
function maxSubArraySumWithKDistinct(nums, k) {
let maxSum = Number.MIN_SAFE_INTEGER;
let currentSum = 0;
let left = 0;
let distinctCount = {};
for (let right = 0; right < nums.length; right++) {
if (!(nums[right] in distinctCount)) {
distinctCount[nums[right]] = 0;
}
distinctCount[nums[right]]++;
currentSum += nums[right];
while (Object.keys(distinctCount).length > k) {
currentSum -= nums[left];
distinctCount[nums[left]]--;
if (distinctCount[nums[left]] === 0) {
delete distinctCount[nums[left]];
}
left++;
}
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
// 测试
const nums = [1,5,4,2,9,9,9];
const k = 3;
console.log(maxSubArraySumWithKDistinct(nums, k)); // 输出 20
```
码小课网站中有更多相关内容分享给大家学习，包括但不限于算法、数据结构、编程技巧等，欢迎大家访问学习。