算法（1）耐心排序

leetcode中有最长递增子序列一题，题目要求很简单，在给的无序数组中求得最长递增子序列的长度。

举个例子nums=[10，9，2，5，3，7，101，18]，那么最长递增子序列是[2,3,7,101]，结果是4。

当然，最长子序列不唯一，但是只要得到长度即可。

最容易想到的算法便是动态规划。思路也很简单，遍历i从第一位开始，在数组【0：i】中以最后一位结尾的最长递增子序列长度是多少。对上述的nums，显然i=2也就是在前三位数字组成的数组中以第三位数字结尾的最长递增子序列长度为1，因为没有数字比2更小，最长递增子序列就是2自己，i=3结果为2，序列为【2，5】，以此类推。

那么以longest数字存储第i位结尾的最长递增序列结果，计算公式也很简单，遍历之前的longest[j]，在所有小于num【i】的num【j】中（这样num【i】就能接在longest【j】对应的序列后面），找出最大的longest【j】加1即可。最后遍历longest数组找到最大的值即使答案。

#include <iostream>
#include <algorithm>
using namespace std;
int longestIncreasingSubsequence(int a[], int length);

int main()
{
    int a[] = { 10,9,2,5,3,7,101,18 };//新建无需数组
    int result = longestIncreasingSubsequence(a, 8);
    cout << result << endl;
}

int longestIncreasingSubsequence(int a[], int length) {
    int *longest = new int[length];//建立数组存储结果
    for (int i = 0; i < length; i++) {
        longest[i] = 1;//初始化为1
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) {
                longest[i] = max(longest[i], longest[j] + 1);
            }
        }
    }
    int res = 1;
    for (int i = 1; i < length; i++) {
        res = max(res, longest[i]);
    }
    return res;
}

动态规划的时间复杂度是O（n^2），然而还有一种算法能做到O(nlogn)，那就是耐心排序，以算法书上的扑克牌举例

算法很巧妙，那么为什么堆数就是最长递增序列的长度呢？

首先思考放牌规则我们模拟取牌的操作（取牌即等价于寻找最长递增序列）能得出以下几个结论：

• 1可以从任一堆中开始取牌
• 2下一张牌不能是同堆的牌（比当前牌大的一定在上方，即在数组中在当前数字前面，不能向前选）
• 3下一张牌不能向前面的堆取（前面堆中比当前牌大的一定在数组中先出现，只是由于该牌的下面又盖上了小牌导致当前牌只能放在右边）

因此取牌的顺序只能是向右面的堆取，那么最长的序列一定是从左到右一堆取一张，但是不可想当然的认为最长递增序列就是每堆的最下面一张牌从左到右连起来，因为这些牌在数组中并不一定符合从前到后的出现顺序。所以我们还要证明能够做到一堆取一张构成最长递增序列。

要证明一定能一堆取一张，只要证明对任一一个堆，一定能找出一张牌，比前一个堆的一张牌大且在数组中排在后面

这也很好证明，放牌时每一张牌一定比前一堆的最后一张牌要大且排在后(第二张图就是从后向前，每张牌对应的当时前堆最后一张牌，看图可以知道最长递增序列有三个解)，也就自然满足上面说的这个条件。

自此我们就能证明堆数就是最长递增序列的长度

接下来只要模拟放牌的过程

注意到每堆的最下面那张牌（也就是堆顶）从左到右是递增的，那么就可以使用二分搜索法最大化效率

由于题目只要求得长度而不需给出序列，所以我们连堆都不用记录，只记录堆顶即可。

函数代码如下：

int patienceSorting(int a[], int length) {
    int* top = new int(length);//记录堆顶
    int piles = 0;//记录堆数
    for (int i = 0; i < length; i++) {
        int poker = a[i];//当前牌
        //二分搜索
        int left = 0, right = piles;
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] > poker)
                right = mid;
            else if (top[mid] < poker)
                left = mid + 1;
            else
                right = mid;
        }
        if (left == piles) 
            piles++;//需要新建堆的情况
        top[left] = poker;
    }
    return piles;
}

二分搜索下次补上