ผลรวมสูงสุดของซับอาร์เรย์สองอันที่ไม่ทับซ้อนขนาดที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็มบวกและตัวเลข k งานของเราคือสร้างโปรแกรมที่จะหาผลรวมสูงสุดของซับอาร์เรย์สองอันที่ไม่ทับซ้อนของขนาดที่กำหนด (k)

โดยพื้นฐานแล้ว เราต้องพิมพ์ซับอาร์เรย์สองอันที่ไม่ทับซ้อน (ต่างกัน) ที่มีผลรวมสูงสุดและมีขนาด k

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต -

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

เอาต์พุต -

{7, 1} , {6, 9}

คำอธิบาย -

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}

ในการแก้ปัญหานี้ วิธีแก้ปัญหาง่ายๆ จะเป็นการหาซับอาร์เรย์ทั้งหมดและผลรวมของพวกเขาแล้วตรวจสอบซับอาร์เรย์สองอันที่มีค่าสูงสุดซึ่งไม่ทับซ้อนกัน

วิธีแก้ปัญหาที่มีประสิทธิภาพในการแก้ปัญหาจะเป็นการใช้ prefix sum array ซึ่งเก็บผลรวมขององค์ประกอบทั้งหมดจนถึงองค์ประกอบของอาร์เรย์ และตรวจสอบ k องค์ประกอบซับอาร์เรย์เพื่อหาซับอาร์เรย์ที่มีผลรวมสูงสุด

ตัวอย่างโค้ด

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้:

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

ผลลัพธ์

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