Untitled
unknown
plain_text
a month ago
3.2 kB
3
Indexable
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]; } }
Editor is loading...
Leave a Comment