Untitled

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int n, K;
    private Map<Integer, Integer> memo;

    private int maxScoreUtilRecursionMemo(int[] nums, int idx) {
        if (idx == n - 1) {
            return nums[idx];  // Base case: last index
        }
        if (memo.containsKey(idx)) {
            return memo.get(idx);  // Return memoized result
        }

        int maxScore = Integer.MIN_VALUE;
        for (int i = idx + 1; i <= Math.min(idx + K, n - 1); i++) {
            maxScore = Math.max(maxScore, maxScoreUtilRecursionMemo(nums, i));
        }

        memo.put(idx, nums[idx] + maxScore);
        return memo.get(idx);
    }

    public int maxResult(int[] nums, int k) {
        this.n = nums.length;
        this.K = k;
        this.memo = new HashMap<>();
        return maxScoreUtilRecursionMemo(nums, 0);
    }
}


class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n]; // dp[i] stores max score to reach index i
        dp[n - 1] = nums[n - 1]; // Base case

        for (int i = n - 2; i >= 0; i--) {
            int maxScore = Integer.MIN_VALUE;
            for (int j = i + 1; j <= Math.min(i + k, n - 1); j++) {
                maxScore = Math.max(maxScore, dp[j]);
            }
            dp[i] = nums[i] + maxScore;
        }
        
        return dp[0]; // Return the max score starting from index 0
    }
}

import java.util.PriorityQueue;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]); // Max-Heap (sorted by dp value)

        dp[n - 1] = nums[n - 1];
        maxHeap.offer(new int[]{dp[n - 1], n - 1}); // Store {dp value, index}

        for (int i = n - 2; i >= 0; i--) {
            // Remove out-of-bound elements from heap (j > i+k)
            while (!maxHeap.isEmpty() && maxHeap.peek()[1] > i + k) {
                maxHeap.poll();
            }

            // Get max dp[j] from heap
            dp[i] = nums[i] + maxHeap.peek()[0];

            // Push {dp[i], i} into the heap
            maxHeap.offer(new int[]{dp[i], i});
        }

        return dp[0];
    }
}


import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        Deque<Integer> deque = new LinkedList<>();

        dp[n - 1] = nums[n - 1];
        deque.addLast(n - 1);

        for (int i = n - 2; i >= 0; i--) {
            // Get max from deque
            dp[i] = nums[i] + dp[deque.peekFirst()];

            // Maintain decreasing order in deque
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }

            // Add current index to deque
            deque.addLast(i);

            // Remove out-of-bound elements
            if (deque.peekFirst() > i + k) {
                deque.pollFirst();
            }
        }
        return dp[0];
    }
}