目錄

問題描述

輸入格式

輸出格式

輸入樣例

輸出樣例

說明

數據范圍

解題思路：

問題理解

數據結構選擇

算法步驟

具體步驟

代碼實現：?

1.特判：?不需要刪除元素的時候

?2.在前面的判斷結束后：k+1，，這是為了應對需要減去一個數字的時候（要保證減了之后剩k個數）

?3.然后就進行滑動窗口計數

?4.枚舉找到最小值：

?最終代碼：

運行結果：?編輯?

---

?

問題描述

給定整數數組，我們稱其中連續的0個或多個整數為一個子數組，求刪除任一元素后，新數組中長度為k的子數組的和的最大值。

輸入格式

• 第一行輸入為N和K，N代表數組長度，K代表子數組長度
• 第二行輸入為N個整數，依次為數組的每個元素

輸出格式

一個整數S，代表所有可能新數組中長度為K的子數組的和的最大值。

輸入樣例

5 3  
2 1 3 -1 4

輸出樣例

8

說明

選擇刪除第四個元素，新數組為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）可以有效地減少計算時間。

算法步驟

1. 計算前綴和：首先計算原始數組的前綴和數組，這樣可以快速計算任意子數組的和。
2. 枚舉刪除元素：對于每個可能刪除的元素，計算刪除該元素后的新數組中長度為?k?的子數組的和。
3. 更新最大值：在枚舉過程中，記錄并更新最大子數組和。

具體步驟

1. 前綴和數組：

   • 創建一個前綴和數組?prefix_sum，其中?prefix_sum[i]?表示從數組開頭到第?i?個元素的和。
   • prefix_sum[i] = prefix_sum[i-1] + nums[i]。

2. 刪除元素后的子數組和：

   • 對于每個元素?nums[i]，計算刪除該元素后的新數組中長度為?k?的子數組的和。
   • 刪除?nums[i]?后，新數組中長度為?k?的子數組的和可以通過前綴和數組快速計算。

3. 更新最大值：

   • 在枚舉刪除元素的過程中，記錄并更新最大子數組和。

?

代碼實現：?

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 herestd::cout << (solution(5, 3, {2, 1, 3, -1, 4}) == 8) << std::endl;return 0;
}

運行結果：?

?

?

?

?