题目描述

最大子数组 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 示例代码

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 示例代码

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 示例代码

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

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法、数据结构、编程技巧等，欢迎大家访问学习。