The minimum contiguous amount that can be obtained by executing no more than K swaps

Question

I have this homework:

For an array of integers N , you need to print the minimum continuous amount that can be obtained by doing no more than K swaps. During a swap, any 2 elements of this array can be replaced.

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 a minimum amount without any swappings, but how can I improve 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 are not sure of the correctness even without a swap.

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

I hope that my decision is not the best, and there is a better approach.

A simple solution of complexity O (N ^ 3).

Suppose that our final minimum adjacent segment is [L, R] for some 0 <= L <= R <N. Now we have two multisets: A and B. A is a multiset with "internal" numbers (numbers within the range [ L, R]) and B is a multiset with "external" numbers (numbers outside the range [L, P]). The goal is to minimize the sum of the numbers in - the sum (A). Creating a swap inside A or B makes sense because it will not affect the sum (A). We can exchange one element from A to another element in B. We have no more than K swaps, and this means that no more than K elements in will swap with no more than K elements in B. To achieve the minimum value of the sum (A ) we take some maximal elements in and replace them with minimal elements in B. For example:

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

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

The answer is the sum (A) == -11

For the range [L, R] we can get the smallest possible sum. To get an answer to our initial problem, we will iterate over all possible ranges [L, R]. 0 <= L <= R <N

Naive implementation. O (N ^ 3logn).

 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

Suppose that for the range [L, R] we already know the sorted set A and the inverse sorted set B. When we calculate for the range [L, R + 1], exactly one element will be removed from B and inserted into (this number exactly matches values ​​of [R + 1]). In C ++, containers and a multiset are installed, which allows us to insert and delete time in O (log) and iterate in O (n) time. Other programming languages ​​also have the same containers (in java it is TreeSet / SortedSet). Therefore, when we move R to R + 1, we will make some simple queries on the multiset (insert / remove).

O (N ^ 3).

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