java - 最多 K 次交换的最小连续总和的程序是什么

Question

我有一个数组 {-1,2,3,4,-3,-2,1,5}

现在我想找到给定数组的最小连续总和子数组，最多 K 次交换。

在上面的数组中，最小连续和是-5，子数组是{-3,-2}

对于 K=1 我应该如何交换元素

1. 我应该交换子数组 i,e 的左边元素吗？交换 a[3] 处的元素 4 与 -1 留给它(再次与哪个数字(子问题在我脑海中弹出)?

   一个。是否是剩余元素中最低的(使用剩余元素的任何排序技术，不包括子数组)。如果我这样做，我会将 -1 与 4 交换，最小和将为 {-1,-3,-2} 根据“atmost”K 交换，我可以只用一次交换返回这个子数组，即使数组有多长

   <

2. 我是否应该将 a[6] 位置的元素 1 替换为 -1 并获得子数组 min总和为 {-3,-2,-1}。再次关注上述 a 点的相同问题。

我想用递归来完成整个过程。因为我正在处理带有 N 整数的数组。我应该遵循递归或迭代的最佳方法是什么？

Answer 1

导入 java.io.; 导入 java.util.;

类测试类{

   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;

}