跳跃游戏 VI

/*
 * 思路：
 * 使用Java Stream无法直接实现此算法，因为它涉及到动态规划和双端队列的操作。
 * 但是我们可以使用Java Stream的api来简化数组的初始化等步骤。
 */
import java.util.*;
import java.util.stream.*;

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

        for (int i = 1; i < n; i++) {
            dp[i] = nums[i] + dp[deque.peekFirst()];
            while (!deque.isEmpty() && dp[i] >= dp[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
            if (i - deque.peekFirst() >= k) {
                deque.pollFirst();
            }
        }

        return dp[n - 1];
    }
}