資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢大小為 k 的子陣列的最大（或最小）和
在這個問題中，我們給定一個數組 arr[] 和一個數字 k。我們的任務是查詢大小為 k 的子陣列的最大（或最小）和。
讓我們舉個例子來理解這個問題，
輸入：arr[] = {55, 43, 12, 76, 89, 25, 99} , k = 2
輸出：165
解釋
大小為 2 的子陣列的和 = 76 + 89 = 165
解決方案方法
解決此問題的一種簡單方法是找到所有大小為 k 的子陣列，然後返回具有最大值的和。
另一種方法是使用滑動視窗，我們將找到大小為 k 的子陣列的和。對於下一個大小為 k 的子陣列，我們將減去最後一個索引元素並新增下一個索引元素。
然後返回具有最大值的子陣列和。
程式說明解決方案的工作原理，
示例
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i=0; i<k; i++)
maxSum += arr[i];
int curr_sum = maxSum;
for (int i=k; i<n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55, 43, 12, 76, 89, 25, 99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<"The sum of subarray with max sum of size "<<k<<" is "<<findMaxSumSubarray(arr, n, k);
return 0;
}輸出
The sum of subarray with max sum of size 2 is 165
更新於： 2021年1月25日
340 次檢視
廣告