当前位置：首页 > article >正文

AI刷题-子数组和的最大值问题

article 2025/2/11 13:33:49

问题描述

输入格式

输出格式

输入样例

输出样例

说明

数据范围

解题思路：

问题理解

数据结构选择

算法步骤

具体步骤

代码实现：

1.特判：不需要删除元素的时候

2.在前面的判断结束后：k+1，，这是为了应对需要减去一个数字的时候（要保证减了之后剩k个数）

3.然后就进行滑动窗口计数

4.枚举找到最小值：

最终代码：

运行结果：编辑

问题描述

给定整数数组，我们称其中连续的0个或多个整数为一个子数组，求删除任一元素后，新数组中长度为k的子数组的和的最大值。

输入格式

第一行输入为N和K，N代表数组长度，K代表子数组长度
第二行输入为N个整数，依次为数组的每个元素

输出格式

一个整数S，代表所有可能新数组中长度为K的子数组的和的最大值。

输入样例

5 3  
2 1 3 -1 4

输出样例

说明

选择删除第四个元素，新数组为2 1 3 4，其长度为3的子数组的和是8。

数据范围

50% case：1≤K<N≤100,−100≤arr[i]≤1001≤K<N≤100,−100≤arr[i]≤100
100% case：1≤K<N≤1×106,−100≤arr[i]≤1001≤K<N≤1×106,−100≤arr[i]≤100

解题思路：

问题理解

我们需要在一个整数数组中，删除一个元素后，找到新数组中长度为 k 的子数组的和的最大值。

数据结构选择

由于我们需要频繁地计算子数组的和，使用前缀和数组（Prefix Sum Array）可以有效地减少计算时间。

算法步骤

计算前缀和：首先计算原始数组的前缀和数组，这样可以快速计算任意子数组的和。
枚举删除元素：对于每个可能删除的元素，计算删除该元素后的新数组中长度为 k 的子数组的和。
更新最大值：在枚举过程中，记录并更新最大子数组和。

具体步骤

前缀和数组：
- 创建一个前缀和数组 prefix_sum，其中 prefix_sum[i] 表示从数组开头到第 i 个元素的和。
- prefix_sum[i] = prefix_sum[i-1] + nums[i]。
删除元素后的子数组和：
- 对于每个元素 nums[i]，计算删除该元素后的新数组中长度为 k 的子数组的和。
- 删除 nums[i] 后，新数组中长度为 k 的子数组的和可以通过前缀和数组快速计算。
更新最大值：
- 在枚举删除元素的过程中，记录并更新最大子数组和。

代码实现：

1.特判：不需要删除元素的时候

// 如果数组长度恰好为 k，不需要删除元素
    if (n == k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

2.在前面的判断结束后：k+1，，这是为了应对需要减去一个数字的时候（要保证减了之后剩k个数）

k++;

3.然后就进行滑动窗口计数

// 滑动窗口计算长度为 k 的最大和
    int maxSum = INT_MIN, windowSum = 0, min = nums[0];
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
        min = std::min(min, nums[i]);
    }
maxSum = windowSum - min;

4.枚举找到最小值：

// 枚举找到最小值
    for (int i = k; i < n; i++) {
        windowSum += nums[i] - nums[i - k];
        min = nums[i];
        for (int j = i - k + 1; j <= i; j++) {
            min = std::min(min, nums[j]);
        }
        maxSum = std::max(maxSum, windowSum - min);
    }

最终代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int solution(int n, int k, const std::vector<int>& nums) {
	// 如果数组长度恰好为 k，不需要删除元素
	if (n == k) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		return sum;
	}
	k++;
	
	// 滑动窗口计算长度为 k 的最大和
	int maxSum = INT_MIN, windowSum = 0, min = nums[0];
	for (int i = 0; i < k; i++) {
		windowSum += nums[i];
		min = std::min(min, nums[i]);
	}
	maxSum = windowSum - min;
	
	// 枚举找到最小值
	for (int i = k; i < n; i++) {
		windowSum += nums[i] - nums[i - k];
		min = nums[i];
		for (int j = i - k + 1; j <= i; j++) {
			min = std::min(min, nums[j]);
		}
		maxSum = std::max(maxSum, windowSum - min);
	}
	
	return maxSum;
}

int main() {
	// Add your test cases here
	std::cout << (solution(5, 3, {2, 1, 3, -1, 4}) == 8) << std::endl;
	return 0;
}