# 4.7. [응용3] Longest Increasing Subsequence (LIS)

Problem
- Given a sequence A=(a[0], a[1],...,a[n-1]), find the length of the longest subsequence such that all elements of the subsequence are sorted increasing order.
Example
- (10, 22, 9, 33, 21, 50, 41, 60, 80)→(10, 22, 33, 50, 60, 80)
- (0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)→(0, 2, 6, 9, 11, 15), \\(0, 4, 6, 9, 11, 15) \\...
Algorithm
- Let d[i] be the length of the LIS that ends in the element at index i. Then, the answer to the LIS problem is the maximum value of d[i], i=0,1,...,n-1
Optimal substructure
- d[i] = \max(1, \max_{j=0,...,n-1 / a[j]<a[i]}{(d[j]+1)}) when i=0,1,..., n-1

code

int LIS(int *a, int N)
{

    int *best, *prev, i, j, max = 0;

    best = (int *)malloc(sizeof(int) * N);
    prev = (int *)malloc(sizeof(int) * N);
    for (i = 0; i < N; i++)
        best[i] = 1, prev[i] = i;

    for (i = 1; i < N; i++)
        for (j = 0; j < i; j++)
            if (a[i] > a[j] && best[i] < best[j] + 1)
                best[i] = best[j] + 1, prev[i] = j;
    for (i = 0; i < N; i++)
        if (max < best[i])
            max = best[i];

    // Print the LIS using prev[] here. free( best ); free( prev );
    return max;
}

# Minimal Triangulation

[A. Aho, J. Hopcroft, and J. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983. 10.2]
Problem
- Given a set of n vertices for convex polygon, find a triangulation such that no two chords cross each other, and the total length of the chords selected is a minimum.
Counting all possible selections of chords in an inefficient way results in an exponential algorithm.

alg