Minimum contiguous sum that can be obtained by performing at most K swaps

Question

I have this homework:

Given an array consisting of N integers, you are required to print the minimum contiguous sum that can be obtained by performing at most K swaps. During a swap any 2 elements of the given array could be swapped.

I tried this

int currentSum = 0;
int currentMin = 0;

for (int j = 0; j < input.Length; j++)
{
    if (input[j] >= 0)
        continue;
    currentSum += input[j];

    if (currentMin > currentSum)
        currentMin = currentSum;
}

It will give the minimum sum without any swappings, but how can I improve in no more than K swaps?

Answer 1

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.Collections;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;


class TestClass {

       static Scanner scanner;
        public static void main(String args[] ) throws Exception {


        scanner=new Scanner(System.in);
        int T=scanner.nextInt();

        while(T>0){
        int N=scanner.nextInt();
        int K=scanner.nextInt();
        int[] array=new int[N];
         for(int i=0;i<array.length;i++)
         {
            array[i]=scanner.nextInt();
        }


         System.out.println(findingMinimumSumSubarray(array, K));

            T--;
        }


    }

    public static int findingMinimumSumSubarray(int[] values, int k) {
     int N = values.length;
     int res = values[0]; 
     for (int L = 0; L < N; L++) {
         for (int R = L; R < N; R++) {
             List<Integer> A= new ArrayList<Integer>();
             List<Integer> B = new ArrayList<Integer>(); 
             int ashu = 0; 
             for (int i = 0; i < N; i++) {
                 if (i >= L && i <= R) {
                  A.add(values[i]);
                     ashu += values[i];
                 } else {
                     B.add(values[i]);
                 }
             }

             Collections.sort(A);

             Collections.sort(B);
             Collections.reverse(B);
             res = Math.min(res, ashu); 
             for (int t = 1; t <= k; t++) {

                 if (t > A.size() || t > B.size()) break;

                 ashu -= A.get(A.size() - t);
                 ashu += B.get(B.size() - t);
                 res = Math.min(res, ashu);
             }
         }
     }
     return res;
 }
}

Answer 2

You solution is not correct even without swap.

Test: [-1, 2, -1]. Your answer on this test is -2. Correct answer: -1

I hope that my solution is not best and there is better approach.

Simple O(N^3) complexity solution.

Let's assume that our final minimum contiguous segment will be [L, R] for some 0 <= L <= R < N. Now we have two multiset: A and B. A - multiset with "inner" numbers (numbers that are inside range [L, R]) and B - multiset with "outer" numbers (numbers that are outside of range [L, R]). Out goal is to minimize sum of numbers in A - sum(A). Making swap inside A or B is meaningful, because it will not affect to sum(A). We can swap one element from A with other element in B. We have no more than K swaps, and it means that no more than K elements in A will be swapped with no more than K elements in B. To reach minimum value of sum(A) we will take some maximum elements in A and swap them with minimum elements in B. For example:

A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; K = 2;

• We can make 0 swaps, A = {-3, -3, -1, 2}; B = {-4, 1, 3, 6}; then sum(A) == -3
• We can make 1 swaps, A = {-3, -3, -1, -4}; B = {2, 1, 3, 6}; then sum(A) == -11
• We can make 2 swaps, A = {-3, -3, 1, -4}; B = {2, -1, 3, 6}; then sum(A) == -9

Answer is sum(A) == -11

For range [L, R] we can get minimum possible sum. To obtain answer for our initial problem we will iterate over all possible ranges [L, R]. 0 <= L <= R < N

Naive implementation. O(N^3logn) complexity.

int get_minimum_contiguous_sum(vector <int> values, int k) {
    int N = values.size();
    int ans = values[0]; // initializing with any possible sums
    for (int L = 0; L < N; L++) {
        for (int R = L; R < N; R++) {
            vector <int> A, B; // our "inner" and "outer" sets
            int suma = 0; // will store initial sum of elements in A
            for (int i = 0; i < N; i++) {
                if (i >= L && i <= R) {
                    A.push_back(values[i]);
                    suma += values[i];
                } else {
                    B.push_back(values[i]);
                }
            }
            // Sorting set A in non-descending order
            sort(A.begin(), A.end());
            // Sorting set B in non-increasing order
            sort(B.begin(), B.end());
            reverse(B.begin(), B.end());
            ans = min(ans, suma); // Updating answer with initial state
            // Iterating number of swaps that we will make
            for (int t = 1; t <= k; t++) {
                // if some of two sets contain less than t elements
                // then we cannot provide this number of swaps
                if (t > A.size() || t > B.size()) break;
                // Swapping t-th maximum of A with t-th minimum of B
                // It means that t-th maximum of A subtracts from suma
                // and t-th minimum of B added to suma
                suma -= A[A.size() - t];
                suma += B[B.size() - t];
                ans = min(ans, suma);
            }
        }
    }
    return ans;
}

Optimization

Let's assume that for the range [L, R] we already know sorted set A and reverse sorted set B. When we will compute for the range [L, R + 1] exactly one element will be deleted from B and inserted in A(this number is exactly values[R+1]). C++ has containers set and multiset that can allow us to insert and remove in O(log) time and iterate in O(n) time. Other programming languages also has same containers (in java it is TreeSet/SortedSet). So when we move R to R+1, we will make some simple queries to multiset(insert/remove).

O(N^3) solution.

int get_minimum_contiguous_sum(vector <int> values, int k) {
    int N = values.size();
    int ans = values[0]; // initializing with any possible sums
    for (int L = 0; L < N; L++) {
        // "inner" multiset
        // Stores in non-increasing order to iterate from beginning
        multiset<int, greater<int> > A;
        // "outer" multiset
        // multiset by defaul stres in non-decreasing order
        multiset<int> B;
        // Initially all elements of array in B
        for (int i = 0; i < N; i++) {
            B.insert(values[i]);
        }
        int suma = 0; // Empty set has sum=0
        for (int R = L; R < N; R++) {// Iterate over all possible R
            // Removing element from B and inserting to A
            B.erase(B.find(values[R]));
            A.insert(values[R]);
            suma += values[R];
            ans = min(ans, suma);
            __typeof(A.begin()) it_a = A.begin();
            __typeof(B.begin()) it_b = B.begin();
            int cur = suma;
            for (int i = 1; i <= k; i++) {
                if (it_a != A.end() && it_b != B.end())
                    break;
                cur -= *it_a;
                cur += *it_b;
                ans = min(ans, cur);
                it_a++;
                it_b++;
            }
        }
    }
    return ans;
}