CODEWITHSUNDEEP
carraysalgorithmsorting
Casteurr
Casteurr

Reputation: 956

Algorithm that gets the largest sorted sub array from an array

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. :)

Upvotes: 0

Views: 860

Answers (2)

phant0m
phant0m

Reputation: 16905

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

  • found a better (i.e. smaller) possible last element for some length i
  • otherwise you have found a longer sequence than you have so far.

Upvotes: 5

Pulkit Goyal
Pulkit Goyal

Reputation: 5654

From 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.

Upvotes: 0

Related Questions