I am trying to do something in C and I need an algorithm that returns the largest dimension wise sorted array contained in another array. So, for example if I have the following array:
A[5] = {5, 2, 3, 1, 4}
it should return:
2, 3, 4
and I can't think of any efficient implementation. Got any ideas? Thank you. :)
Your problem is known as "longest increasing subsequence".
An algorithm utilizing dynamic programming can be found here, with a good explanation. It has optimal asymptotic complexity of O(nlogn).
The basic idea is, that you keep track of the best possible last element (or rather the index thereof) for a subsequence with length i. When you process the next element, you check the array m to see whether you have either
iFrom the wikipedia page for Longest increasing subsequence:
L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1)
This isn't C, but should be straightforward to code this in C.
