A subsequence of a given input sequence is any sequence that can be obtained by deleting $0$ or

more elements from the input sequence. We define the sum of a subsequence to be the sum of the

elements in a given subsequence. For this problem, not all subsequences are allowed. A

subsequence is called $"$k$-$smooth" if for each pair of adjacent terms in the subsequence, the absolute

value of their difference does not exceed $k.$ For example, in the sequence given below, the terms

highlighted in yellow for a valid $4-$smooth subsequence:

The Problem

Given a list of $n$ integers and an integer $k,$ determine the maximum k$-$smooth subsequence sum

AND determine a subsequence of the input values that achieves that maximum sum.

The Input

The first line of input contains two integers, $n(1n5000),$ representing the number of integers

in the input list and $k(1k{10}^9),$ the maximum difference allowed between consecutive terms

in the chosen subsequence.

The next line will contain $n$ space separated positive integers, indicating the input list, in order.

Each of these integers will be in between $1$ and ${10}^9,$ inclusive.

The Output

On a line by itself, output the maximum k$-$smooth subsequence sum. On the second line of output,

indicate the $1-$based index of each term in the subsequence.

Sample Input Sample Output

Implementation Hints

Both problems require dynamic programming and have solutions that are somewhat similar in

structure and somewhat short. It's completely fine if your whole solution is in main $($if written as

an iterative DP$),$ or if you just have one memorized function other than main $($if using

memorization$).$ The process by which to generate the "build back" is fairly similar for both

problems, so once you figure one of them out, the other one is likely to take much less time.

CODE IN JAVA