arrays - 执行至多K次交换可以获得的最小连续和

Question

我有这个作业:

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.

我试过了

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

它会在没有任何交换的情况下给出最小总和，但是我怎样才能在不超过 K 次交换的情况下提高呢？

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