Untitled

mail@pastecode.io avatar
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