I again follow the four step dynamic programming pattern.
1. Define the state (what information dp[] tracks)
You want a subsequence that forms: Let: = The maximum length of a good subsequence that ends with value . That means: among all subsequences you can pick from the array that end in value v, dp[v] stores the longest length achievable. Since values in the array can be as large as , dp must be implemented as a map/hash map, not an array. Before moving to the next unit, think that only DP can't solve the whole problem; something else is also required.