Untitled
unknown
plain_text
13 days ago
1.6 kB
4
Indexable
Never
public static int getMaximumPower(List<Integer> arr, List<Integer> power) { final int MOD = 1000000007; PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2] - a[2]); // Precompute all possible subarray sums for (int i = 0; i < power.size() - 1; i++) { for (int j = i + 1; j < power.size(); j++) { int start = Math.min(power.get(i), power.get(j)); int end = Math.max(power.get(i), power.get(j)); int subarraySum = sumSubarray(arr, start, end - 1); maxHeap.add(new int[]{i, j, subarraySum}); } } int powerSum = 0; Set<Integer> removedIndices = new HashSet<>(); // Perform k/2 operations for (int op = 0; op < power.size() / 2; op++) { while (!maxHeap.isEmpty()) { int[] top = maxHeap.poll(); int i = top[0], j = top[1], subarraySum = top[2]; if (removedIndices.contains(i) || removedIndices.contains(j)) { continue; // Skip if the indices are already removed } powerSum = (powerSum + subarraySum) % MOD; removedIndices.add(i); removedIndices.add(j); break; } } return powerSum; } private static int sumSubarray(List<Integer> arr, int start, int end) { int sum = 0; for (int i = start; i <= end; i++) { sum += arr.get(i); } return sum; }
Leave a Comment