Find the length of the largest increasing sequence

Question

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

Answer 1

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)

Answer 2

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.

Answer 3

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

Answer 4

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