gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-02 19:53:01 28 4
gpt4 key购买 nike

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

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

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

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

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

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

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

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

最佳答案

导入 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;

}

关于java - 最多 K 次交换的最小连续总和的程序是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38801945/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com