Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length $n$, find a longest increasing subsequence.

Brute-force approach:
Enumerate all possible subsequences and then determine which are increasing and store the longest one. This approach is obviously impractical for large $n$ and its time complexity is exponential.

Dynamic programming approach:
The longest increasing subsequence of an array $A$ of length $n$ can be determined based on that of all the prefix arrays. We need use an auxiliary array $T[n]$, in which $T[i]$ stores the length of longest increasing (non-decreasing) subsequence ending at $A[i]$. Notice that is ending at, i.e., the last element must be $A[i]$. Meanwhile, the global maximum length is also stored in variable $L$. The time complexity for this algorithm will be $O(n^2)$.



Related Posts:

$O(n\log n)$ Algorithm for Longest Increasing Subsequence