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