CODEWITHSUNDEEP
javaalgorithm
Sawyer
Sawyer

Reputation: 443

What is the procedure for Minimum contiguous sum with atmost K swaps

I have an array say {-1,2,3,4,-3,-2,1,5}

Now I would like to find the minimum contiguous sum subarray for the given array with atmost K swaps.

In the array above the minimum contiguous sum is -5 and subarray is {-3,-2}

Say for K=1 How should I swap the elements

  1. Should I swap the left element of the sub array i,e; swaping element 4 at a[3] which is left to it with -1 (again with which number (sub question pops up in my mind)?

    a. whether the lowest of the the remaining elements (with any sorting technique of the remaining elements excluding subarrays). If I do this I will swap -1 with 4 and the min sum will be {-1,-3,-2} As per "atmost" K swaps I can return this the subarray with only one swap even how long the array is

  2. Should I swap the element 1 at the postion a[6] with -1 and get the sub array with min sum as {-3,-2,-1}. Again following the same question at point a above.

This whole process I would like to do with recursion. As I am dealing with arrays with N integers. Which is best approach I should follow recursion or iteration?

Upvotes: 3

Views: 547

Answers (1)

NIKHIL MUCHERLA
NIKHIL MUCHERLA

Reputation: 11

import java.io.; import java.util.;

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){
        t--;
    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();
    }
    int ans=findingMinimumSumSubarray(array,k);
     System.out.println(ans);
    }


}

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

         Collections.sort(A);

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

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

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

} }

Upvotes: 1

Related Questions