Tổng lớn nhất hai mảng con không chồng chéo kích thước cho trước trong C++

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

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

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào –

mảng = {7, 1, 6, 9, 2} , k = 2

Đầu ra –

{7, 1} , {6, 9}

Giải thích –

tất cả mảng con kích thước 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
Hai mảng con không chồng chéo với tổng lớn nhất là {7,1} và {6,9}

Để giải quyết bài toán này, một giải pháp đơn giản sẽ 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 lớn nhất không chồng chéo nhau.

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

Ví dụ

Chương trình minh họa triển khai giải pháp của chúng ta:

#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<<"Hai mảng con không chồng chéo với tổng lớn nhất là \n";
    maxSubarray(arr, N, K);
    return 0;
}

Kết quả

Hai mảng con không chồng chéo với tổng lớn nhất là
{ 2 5 }
{ 7 3 }