分享个第四题的代码
题目是：一个长度为n的数组，再给一个k，k<n，问删除任一元素后，剩下的数组中长度为k的子数组最大和为多少?
思路：维护一个区间和，然后就是区间最小值问题，用优先队列算区间最小值。遍历求最大值
代码
下面代码没提交，仅供参考。
package bt;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Q4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(maxSum(n,k,arr));
}
public static long maxSum(int n,int k,int arr[]) {
k++;
PriorityQueue<int[]> pq = new PriorityQueue<>(
(o1,o2) -> {
return o1[0] - o2[0];
}
);
long sum = 0;
for (int i = 0; i < k; i++) {
pq.add(new int[]{arr[i],i});
sum += arr[i];
}
long ans = sum - pq.peek()[0];
System.out.println(ans);
for(int i = k; i < n; i++){
pq.add(new int[]{arr[i],i});
sum += arr[i];
sum -= arr[i-k];
while(pq.peek()[1]<=i-k) pq.poll();
ans = Math.max(ans,sum-pq.peek()[0]);
}
return ans;
}
}
全部评论
(9) 回帖