Partition into two subarrays of lengths k and (N – k) such that the difference of sums is maximum

December 30, 2021

Partition into two subarrays

In Partition into two subarrays problem we have to divide elements of the array into two parts such that their difference is maximum. The problem can be solved optimally using greedy approach. In this article, we will provide a C++ solution with an explanation.

Partition into two subarrays of lengths k and (N – k) such that the difference of sums is maximum

Partition into two subarrays Problem Description

Given an array of n integers and an integer k. Partition the array elements into two parts such that size of one part is k & other part is n-k. Each element of the array must be a part of only one set. Partition in such a way that the difference between two parts is maximum possible. Output the maximum difference.

Input:

  • First-line contains two integers n & k.
  • The next Line contains n integers the elements of the array.

Output:

  • The required difference.

Problem Solution

The problem can be solved using greedy technique. Note that we have to maximize the difference between two parts, this implies we have to maximize sum of one part and minimize the sum of the other part.

To achieve this we will sort the elements in decreasing order and maximize the sum of one part by taking the largest element and maximum number of elements (out of n and n-k).

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int mxDiff(int arr[], int n, int k)
{
    sort(arr, arr + n, greater<int>());

    int totalSum = 0, sum = 0;
    for (int i = 0; i < n; i++)
        totalSum += arr[i];

    int sz = max(k, n – k);
    for (int i = 0; i < sz; i++)
        sum += arr[i];

    return sum – (totalSum – sum);
}
int main()
{
    int n = 6, k = 2;
    int arr[6] = {6, 2, 4, 3, 5, 6};
    cout << mxDiff(arr, n, k) << endl;
}

Output

16

Explanation
partition is {2,3} & {4,5,6,6}