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

Trong bài toán này, chúng ta được đưa ra một mảng các số nguyên dương và một số k. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm tổng tối đa của hai mảng con không trùng nhau có kích thước đã cho (k).

Vì vậy, về cơ bản chúng ta có hai in hai mảng con không chồng chéo (riêng biệt) có tổng lớn nhất và có kích thước k.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

array = {7, 1, 6, 9, 2} , k = 2

Đầu ra -

{7, 1} , {6, 9}

Giải thích -

all subarrays of size 2.
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11
Two non-overlapping subarrays with max sums are {7,1} and {6,9}

Để giải quyết vấn đề này, một giải pháp đơn giản là tìm tất cả các mảng con và tổng của chúng, sau đó kiểm tra hai mảng con tối đa không trùng nhau.

Một cách tiếp cận hiệu quả để giải quyết vấn đề sẽ là sử dụng mảng tổng tiền tố lưu trữ tổng của tất cả các phần tử cho đến phần tử của mảng. Và kiểm tra k phần tử của các mảng con để tìm mảng con có tổng lớn nhất.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
   if (i == 0)
      return sum[j];
   else
      return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
   int prefixsum[N];
   prefixsum[0] = arr[0];
   for (int i = 1; i < N; i++)
   prefixsum[i] = prefixsum[i - 1] + arr[i];
   pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
   int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
   pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
   for (int i = N - 2 * K - 1; i >= 0; i--){
      int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
      if (cur >= secondSubarrayMax.second)
         secondSubarrayMax = make_pair(i + K, cur);
      cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
      if (cur >= maxSubarraySum){
         maxSubarraySum = cur;
         resIndex = make_pair(i, secondSubarrayMax.first);
      }
   }
   cout<<"{ ";
   for (int i = resIndex.first; i <resIndex.first + K; i++)
      cout<<arr[i]<<" ";
   cout<<"}"<<endl<<"{ ";
   for (int i = resIndex.second; i < resIndex.second + K; i++)
      cout<<arr[i]<<" ";
   cout<<"}"<<endl;
}
int main(){
   int arr[] = {2, 5, 1, 2, 7, 3, 0};
   int N = sizeof(arr) / sizeof(int);
   int K = 2;
   cout<<"Two non-overlapping subarrays with maximum sum are \n";
   maxSubarray(arr, N, K);
   return 0;
}

Đầu ra

Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 }