Tổng tối đa của M mảng con không chồng chéo có kích thước K trong C ++

Tuyên bố vấn đề

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

Ví dụ

Nếu mảng Cho trước là ={2, 10, 7, 18, 5, 33, 0}. N =7, M =3 và K =1 thì đầu ra sẽ là 61 vì tập con là -

{33, 18, 10}

Thuật toán

• Chúng tôi tạo một mảng đặt trước, chứa trong mỗi tổng chỉ số của tất cả các phần tử từ 'chỉ số' đến 'chỉ số + K' trong mảng đã cho. Và kích thước của mảng tổng sẽ là n + 1-k
• Bây giờ nếu chúng ta bao gồm mảng con có kích thước k, thì chúng ta không thể đưa lại bất kỳ phần tử nào của mảng con đó vào bất kỳ mảng con nào khác vì nó sẽ tạo ra các mảng con chồng chéo lên nhau. Vì vậy, chúng tôi thực hiện cuộc gọi đệ quy bằng cách loại trừ k phần tử của các mảng con được bao gồm
• nếu chúng ta loại trừ một mảng con thì chúng ta có thể sử dụng k-1 phần tử tiếp theo của mảng con đó trong các mảng con khác, vì vậy chúng ta sẽ thực hiện lệnh gọi đệ quy chỉ bằng cách loại trừ phần tử đầu tiên của mảng con đó.s
• Cuối cùng, trả về giá trị tối đa (tổng được bao gồm, tổng bị loại trừ)

Ví dụ

#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 bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Đầu ra

Maximum sum = 61