最长单调递增子序列（LIS）

最长单调递增子 序列，就是在一个数列中最长的按单调递增的顺序排列的序列，该序列在原序列中可以不连续。

解法1:

设b[i]为截止到第i个数且以第i个数为结尾的最长单调递增子序列的长度，a为所给序列，则有：

Initial condittion:
b[0]  = 1
Recurrence relation:

b[ i ] = max( a[i] > a[j] ? b[j] + 1 : 1)    j = 0...i-1

//return value: length of LIS
//aMax: LIS array
//a: original array
//b: b[i] stores the length of the local LIS with the last member a[i]
//p: p[i] stores the previous index of member of the local LIS with the last member a[i]

int LIS(int *a, int *b, int *p, int *aMax, int n)
{
    int max = 0;
    int maxIndex;

    for(int i = 0; i < n; i++)
    {
        b[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[i] > a[j] && b[i] < b[j] + 1)
            {
                b[i] = b[j] + 1;
                p[i] = j;
            }
        }

        if(b[i] > max)
        {
            max = b[i];
            maxIndex = i;
        }
    }

    for(int i = max -1; i > -1;  i--)
    {
        aMax[i] = a[maxIndex];
        maxIndex = p[maxIndex];
    }

    return max;
}

复杂度o(n2)

解法2:

将原序列按升序排序，再对原序列和排序后的序列计算LCS(Longest Common Subsequence）的长度。

排序复杂度o(nlogn), LCS复杂度o(n2), 总复杂度o(n2)