資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中大小為K的M個不相交子陣列的最大和
問題陳述
給定一個數組和兩個數字M和K。我們需要找到陣列中大小為K的M個最大子陣列（不相交）的和。（陣列順序保持不變）。K是子陣列的大小，M是子陣列的個數。可以假設陣列的大小大於m*k。如果陣列總大小不是k的倍數，則我們可以取部分最後一個數組。
示例
如果給定陣列為 = {2, 10, 7, 18, 5, 33, 0}，N = 7，M = 3，K = 1，則輸出將為61，子集為：
{33, 18, 10}演算法
- 我們建立一個字首和陣列，該陣列的每個索引都包含給定陣列中從“索引”到“索引+K”的所有元素的和。和陣列的大小將為n+1-k
- 現在，如果我們包含大小為k的子陣列，那麼我們不能再次在任何其他子陣列中包含該子陣列的任何元素，因為它會建立重疊的子陣列。因此，我們透過排除包含的子陣列的k個元素來進行遞迴呼叫
- 如果我們排除一個子陣列，那麼我們可以在其他子陣列中使用該子陣列的接下來的k-1個元素，因此我們將透過只排除該子陣列的第一個元素來進行遞迴呼叫。
- 最後返回最大值(包含的和, 排除的和)
示例
#include <bits/stdc++.h>
using namespace std;
void calculatePresumArray(int presum[], int arr[], int n, int k) {
for (int i = 0; i < k; i++) {
presum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++) {
presum[i] += presum[i-1] + arr[i+k-1] - arr[i- 1];
}
}
int maxSumMnonOverlappingSubarray(int presum[], int m, int size, int k, int start) {
if (m == 0)
return 0;
if (start > size - 1)
return 0;
int mx = 0;
int includeMax = presum[start] + maxSumMnonOverlappingSubarray(presum, m - 1, size, k, start + k);
int excludeMax = maxSumMnonOverlappingSubarray(presum, m, size, k, start + 1);
return max(includeMax, excludeMax);
}
int main() {
int arr[] = { 2, 10, 7, 18, 5, 33, 0 };
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3, k = 1;
int presum[n + 1 - k] = { 0 };
calculatePresumArray(presum, arr, n, k);
cout << "Maximum sum = " << maxSumMnonOverlappingSubarray(presum, m, n + 1 - k, k, 0) << endl;
return 0;
}編譯並執行上述程式時，將生成以下輸出：
輸出
Maximum sum = 61
更新於：2019年12月20日
209 次瀏覽
廣告