Find out multiple nonintersecting increasing sequences in an array of maximal combined length

There is a known problem "Longest increasing subsequence", which is: Given an array of integers, find out the longest increasing sequence in that array. I now face a similar but apparently more complicated problem: Given an array of integers and a given number N, find N sequences in that array so that each of them is increasing, they do not intersect by indexes and their combined sum of lengths is maximal.

So far I have tried "greedy" algorithms in the line of:

1. Use the longest increasing subsequence algorithm, throw that sequence away from the array, repeat N times, provide found sequences as result. This works if N=1 by design, works in several odd cases but returns incorrect results for shuffled arrays such as an array constructed of N increasing subsequences.
2. Construct a number of sequences, adding each element to the now-longest possible subsequence. Obviously flawed, as it finds "substrings" more often than prolonged sequences.
3. Construct a number of sequences, adding each element to the sequence that has the largest last element. This works better, at least if an array is known to contain N increasing subsequences, this algorithm correctly returns full array as the result, but it does not work properly in general, as it does not consume N as is.

Any other ideas?