Help me to solve this question

1

An array X consists of N integers. The indices of any two elements of the array can be swapped with each other.

Write a program to find the minimum contiguous sum of the elements of the array that is obtained by performing a maximum of K swaps in the array.
(The resulting contiguous sub-array that is selected for the optimal answer should not be empty).

Input format

  • First line: T (Number of test cases)
  • First line in each test case: N and K
  • Second line in each test case: N space-separated integers (denoting the elements of the array X )

Output format
For each test case, print the minimum contiguous sum of the elements that is obtained by performing at most K swaps.

question link: here

p.s. : the question is from a challenge that is over now : )

my approach is to select k smallest elements from the array, but it’s not working…

can anyone share the approach for this question?

2

Input :
2
3 2
1 -5 2
4 1
3 -2 1 -1

Output :
-5
-3

Explanation :
For second test case we can perform at most 1 swap and if we swap the position of 1 and -1 then we can get the minimum contiguous sum -3.

1 Like
3

Iterate over all possible pairs (l, r). We will calculate the answer if we select subarray [l, r]. Obviously, for our k swaps, we should swap the largest k in [l, r] with the smallest k not in [l, r]. This should all be done in O(n^3) or O(n^3logn).

1 Like
4

can you share the pseudo code for the same?