Split array into K subarrays such that sum of maximum of all subarrays is maximized

#include <bits/stdc++.h>

using namespace std;

  

void partitionIntoKSegments(int arr[],

                            int N, int K)

{

    

    if (N < K) {

        cout << -1 << endl;

        return;

    }

    

    

    map<int, int> mp;

  

    

    

    int temp[N];

  

    

    int ans = 0;

  

    

    for (int i = 0; i < N; i++) {

        temp[i] = arr[i];

    }

  

    

    

    sort(temp, temp + N,

         greater<int>());

  

    

    for (int i = 0; i < K; i++) {

  

        

        ans += temp[i];

  

        

        

        mp[temp[i]]++;

    }

  

    

    vector<vector<int> > P;

  

    

    vector<int> V;

  

    

    for (int i = 0; i < N; i++) {

        V.push_back(arr[i]);

  

        

        

        if (mp[arr[i]] > 0) {

  

            mp[arr[i]]--;

            K--;

  

            if (K == 0) {

                i++;

                while (i < N) {

                    V.push_back(arr[i]);

                    i++;

                }

            }

  

            if (V.size()) {

                P.push_back(V);

                V.clear();

            }

        }

    }

  

    

    cout << ans << endl;

  

    

    for (auto u : P) {

        for (auto x : u)

            cout << x << " ";

        cout << endl;

    }

}

int main()

{

    

    int A[] = { 5, 3, 2, 7, 6, 4 };

    int N = sizeof(A) / sizeof(A[0]);

    int K = 3;

  

    

    partitionIntoKSegments(A, N, K);

    return 0;

}

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets