Let us understand each term one by one.
- Subsequence: It is a collection of elements of a sequence such that they preserve the relative ordering. e.g {4, 7, 9}, {2, 1, 4}, {2, 9} are subsequences of the sequence {1, 2, 1, 4, 5, 7, 8, 9}. However, {5, 4, 7}, {9, 8}, {3} are not subsequences of it.
- Increasing Subsequence: It is a subsequence such that all the elements are in a non-decreasing order. e.g {4, 7, 9}, {2, 9} are increasing subsequence of the sequence {4, 2, 3, 7, 9}.
- Longest Increasing Subsequence: It is the longest length increasing subsequence. e.g {2, 3, 7, 9} is the longest increasing subsequence of {4, 2, 3, 7, 9}.