##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
State and transition
Let be the maximum sum of a subsequence ending at index .
Transition: You either start fresh at (just ) or extend from some within distance .
Naive implementation: because you scan previous states. With monotonic deque: by maintaining max over the sliding window of values.
