Challenge: Max Sum IS Reconstruction

Track predecessors to reconstruct the maximum sum increasing subsequence. When $dp[i] = dp[j] + nums[i]$ is optimal, set $prev[i] = j$.

Find the index with maximum $dp$, then backtrack. Unlike length-based LIS, the maximum might not be at the last position. Scan all $dp$ values to find the best ending index. Try it on $[1, 101, 2, 3, 100, 4, 5]$. The answer ends at index $4$ (value $100$), not index $6$ (value $5$).