CODEWITHSUNDEEP
algorithm
SuperString
SuperString

Reputation: 22519

Find the length of the largest increasing sequence

What's a fast algorithm for finding the length of largest monotonically increasing sequence in an array of integers.

Upvotes: 2

Views: 5728

Answers (4)

chethu
chethu

Reputation: 351

you can use dynamic programming to solve this problem.The solution for this problem using dynamic programming is here:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Upvotes: 1

Mr. Boy
Mr. Boy

Reputation: 63728

As Mehrdad suggests, LIS is at least close to what you need. This is most efficiently implemented using dynamic programming / memoization. If you are interested in stuff like this, I recommend you head over to TopCoder

Upvotes: 1

Michal Ciechan
Michal Ciechan

Reputation: 13888

Not sure what you mean by algorithm but here's an idea.

If the array is sorted by default (i.e when creating array laregst value is at the end due to it being an increasing sequence) then retrieve the last array value.

If not then create a new variable and loop through the array assigning the current value in loop if it is larger than the one stored in the temporary variable.

Upvotes: 0

Mehrdad Afshari
Mehrdad Afshari

Reputation: 421998

From Wikipedia: Longest increasing subsequence (O(n log n))

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)

Upvotes: 3

Related Questions