This could be done with simple greedy algorithm.
Keep sorted array of subsequences found so far. Sorted in decreasing order, by the value of the last integer in each sequence. Initially empty.
Get first not-yet-processed element from the sequence and find the subsequence where the last integer is smaller than this element but larger (or equal) than in all such subsequences. Use binary search here to get overall complexity O(N log N). If no such subsequence found, add a new one at the end of the array. Add this element to this subsequence. Repeat while there are not-yet-processed elements in the sequence.