Tổng lớn nhất của M mảng con không chồng chéo kích thước K trong C++

Đề bài

Cho một mảng và hai số M và K. Cần tìm tổng của M mảng con lớn nhất có kích thước K (không chồng chéo) trong mảng. (Thứ tự mảng không thay đổi). K là kích thước mảng con và M là số lượng mảng con. Có thể giả định kích thước mảng lớn hơn m*k. Nếu tổng kích thước mảng không phải bội số của k, có thể lấy mảng con cuối cùng một phần.

Ví dụ

Nếu mảng cho là = {2, 10, 7, 18, 5, 33, 0}. N = 7, M = 3 và K = 1 thì kết quả sẽ là 61 với tập con là:

{33, 18, 10}

Thuật toán

• Tạo mảng presum, trong đó mỗi chỉ số chứa tổng các phần tử từ 'chỉ số' đến 'chỉ số + K' trong mảng cho trước. Kích thước mảng tổng sẽ là n+1-k.
• Nếu bao gồm mảng con kích thước k, không thể bao gồm bất kỳ phần tử nào của mảng con đó lại trong mảng con khác vì sẽ tạo ra mảng con chồng chéo. Do đó gọi đệ quy bằng cách loại bỏ k phần tử của mảng con đã bao gồm.
• Nếu loại trừ một mảng con, ta có thể dùng k-1 phần tử tiếp theo của mảng con đó trong các mảng con khác, nên gọi đệ quy bằng cách chỉ loại bỏ phần tử đầu tiên của mảng con đó.
• Cuối cùng trả về max(tổng bao gồm, tổng loại trừ).

Ví dụ mã nguồn

#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; }

Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:

Kết quả

Maximum sum = 61