Was mit atmost K Swaps

Question

Ich habe ein Array sagen {-1,2,3,4,-3,-2,1,5}

Nun möchte Ich mag finden, um die minimale sequenzielle Summe Subarray für die gegebene Array mit atmost K Swaps das Verfahren für die minimale sequenzielle Summe ist.

In der Anordnung über der minimalen sequenziellen Summe ist -5 und Sub-Array ist {-3,-2}

Say für K=1 Wie sollte ich tauschen die Elemente

1. Sollte ich das linke Element des Subarray tauschen i, e; swaping Element 4 an a[3] die mit -1 ihm übrig ist (wieder mit der Nummer (sub Frage im Kopf bis POPs)?

   a., ob der niedrigste der die übrigen Elemente (mit einer beliebigen Sortiertechnik der übrigen Elemente Wenn ich dies ohne Sub-Arrays). tun werde ich -1 mit 4 tauschen und die min Summe {-1,-3,-2} per „atmost“ K Swaps sein wird kann ich diese Rückkehr des Sub-Array mit nur einem Swap selbst, wie lange das Array

2. Sollte ich das Element 1 an der Position a[6] mit -1 tauschen und das Sub-Array mit min sum als {-3,-2,-1} bekommen. Wiederum die gleiche Frage zu Punkt a oben.

Dieser ganze Prozess möchte ich mit Rekursion tun. Da es sich um Arrays mit N ganzen Zahlen handelt. Welches ist der beste Ansatz, dem ich Rekursion oder Iteration folgen sollte?

Answer 1

import java.io. ; importieren Sie java.util.;

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

} }