Given a sequence, find a longest increasing subsequence. A longest increasing subsequence is that the subsequences elements are in sorted order, lowest to highest, and in which the subsequence is as long as possiable. A subsequence is not necessarily contiguous, or unique.

For example, consider below sequence: 0, 8, 4, 12, 2, 10, 6,14, 1, 9, 5, 13, 3, 11, 7, 15, a longest subsequence is 0, 2, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15.

Please discuss the principle of optimality by using dynamic programming, and design a recurrence equations. Then use pseudocode to describe the solution.