##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Finding the optimal subsequence
Track predecessors to reconstruct the maximum sum increasing subsequence. When is optimal, set .
Find the index with maximum , then backtrack. Unlike length-based LIS, the maximum might not be at the last position. Scan all values to find the best ending index. Try it on . The answer ends at index (value ), not index (value ).
