資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中包含至少 k 個數的最大子陣列和
讓我們瞭解完成該程式的步驟。
- 初始化陣列。
- 初始化大小為 n 的 max\_sum 陣列。
- 查詢每個索引的最大和並將其儲存在 max\_sum 陣列中。
- 計算所有元素的總和並將其儲存在變數 sum 中。
- 編寫一個從 i = k 到 n 迴圈的迴圈。
- 將 a[i] - a[i - k] 新增到 sum 中。
- 使用結果、和的最大值更新結果。
- 使用結果、和 + max\_sum[i - k] 的最大值更新結果。
示例
讓我們看看程式碼。
#include<bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
int maxSum[n];
maxSum[0] = a[0];
int currentMax = a[0];
for (int i = 1; i < n; i++) {
currentMax = max(a[i], currentMax+a[i]);
maxSum[i] = currentMax;
}
int sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
int result = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i-k];
result = max(result, sum);
result = max(result, sum + maxSum[i-k]);
}
return result;
}
int main() {
int a[] = {5, 3, 7, -5, 6, 2, 1};
int k = 6;
cout << getMaxSum(a, 7, k) << endl;
return 0;
}輸出
如果你執行以上程式碼，你將得到以下結果。
19
結論
如果你對本教程有任何疑問，請在評論區提及。
更新時間：09-Apr-2021
322 次瀏覽
廣告