Untitled

public class MaximumFruits {
    public int maxFruits(int[][] fruits, int startPos, int k) {
        int N = 2 * 100000 + 1;
        int[] prefix = new int[N];

        // Populate prefix array
        for (int[] fruit : fruits) {
            prefix[fruit[0]] += fruit[1];
        }

        // Compute prefix sums
        for (int i = 1; i < N; i++) {
            prefix[i] += prefix[i - 1];
        }

        int maxi = 0;

        // Move to the right
        for (int i = startPos; i <= Math.min(startPos + k, N - 1); i++) {
            int r = i;
            int x = i - startPos;
            int l = Math.max(0, startPos - (k - 2 * x));

            int sum = prefix[r];
            if (l > 0) {
                sum -= prefix[l - 1];
            }

            maxi = Math.max(maxi, sum);
        }

        // Move to the left
        for (int i = startPos; i >= Math.max(0, startPos - k); i--) {
            int l = i;
            int x = startPos - i;
            int r = Math.min(N - 1, startPos + (k - 2 * x));

            int sum = prefix[r];
            if (l > 0) {
                sum -= prefix[l - 1];
            }

            maxi = Math.max(maxi, sum);
        }

        return maxi;
    }

    public static void main(String[] args) {
        MaximumFruits solution = new MaximumFruits();
        int[][] fruits = {{2, 8}, {6, 3}, {8, 6}};
        int startPos = 5, k = 4;

        System.out.println(solution.maxFruits(fruits, startPos, k)); // Output: 9
    }
}