Which values in each subsequence matter? The only values that matter are the maximum and minimum values.

Let the maximum and minimum values of a subsequence be Max and Min. It is optimal to place all values in between Max and Min in the original array in the same subsequence as Max and Min.

Sort the array.