本文适合已经清楚最长上升子序列I的Dp过程但对II的优化存在疑惑的童鞋阅读

最长上升子序列II的第一步优化：

假设现在要求以a[i]字符（虽然是int，但是说数字感觉怪怪的，就说字符吧，下同）结尾的最长上升子序列，暴力解法在进行状态转移的时候是枚举以a[1]~a[i-1](数组下标从1开始）每个字符结尾的最长上升子序列然后每个加1取max，但事实上我们并不需要枚举这么多已知状态，有些状态是多余的

举个例子，假设现在要求以a[i]=2结尾的最长上升子序列,已知f[3]=6,f[5]=6,f[7]=6;显然，因为3>2所以f[3]肯定不可能作为f[2]的状态转移对象（要满足上升要求），而7>5>3，既然3都不能满足要求，比3更大的5和7更不可能，这种情况下我们是完全没有必要再去枚举f[5]和f[7]了；假设现在a[i]=10，显然f[3]是可以作为f[10]的状态转移对象的，同时因为f[5]和f[7]的最长上升子序列长度和f[3]一致，所以也没必要枚举f[5]和f[7]，因为在取max的时候结果不会变

从上面的例子，不难看出，对于长度相等（也就是f值相等）的已知状态，我们只需要保留结尾字符最小的那个状态即可，其余长度相同的状态没必要保留更没必要去枚举，这样，状态转移所需要枚举的已知状态变少了，时间效率自然也就高了

而我们需要清楚地是，这些已知状态之间的关系，在求解当前状态时，我们是已经可以得知的，也就是说我们是可以把那些多余的状态筛掉的

最长上升子序列II的第二步优化：

对找到最佳转移状态进行优化：

接着上面的例子，假设现在我们用一个数组来存储已经筛掉多余的状态的已知状态（其实就是把他们的对应的结尾字符存下来而已），然后我们用一个for去枚举数组里的每个已知状态，进行状态转移（就像暴力解法那样，只不过现在需要枚举的状态少了许多），这样做当然是可以的（感兴趣的童鞋可以自己试一下），只不过这里还可以继续进行优化，降低时间复杂度

如果要继续进行优化，我们自然会想，有没有什么更快的方法可以帮我们找到那个最合适的已知状态（for循环的目的也是如此），想要进行优化，最关键的就是利用已知信息之间的关系，我们上面的第一次优化不也是利用已知信息之间的关系做到的吗？通过观察，我们可以发现，这些被保留下的已知状态，彼此之间的序列长度肯定都不同（这句是废话），而且随着序列长度的增加，结尾字符也不断增大，这是巧合吗?

不妨先假设这个性质存在（证明放在最下面），利用这个性质，我们把刚才那些已知状态按序列长度从小到大排个序，然后找到以比a[i]小的最大字符结尾的状态(这句比较绕，好好理解下），这个状态显然就是我们要的最佳已知状态，因为排在它后面的状态a[i]转移不过去（不满足上升的要求），而在它前面的状态长度比它小没必要转移过去（不满足最长的要求）；而在一个有序序列中查找某个数，我们自然会想到用二分去实现

更新已知状态的绝妙方式：

既然我们已经求出了一个新的状态，自然需要用它去更新一下现有的已知状态，如果这个状态是从最后一个已知状态（排完序之后的）转移过来的，那我们直接把它放在序列尾部即可（因为他的长度是现有已知状态中最长的）；如果它是中间某个状态转移过来的，这里为了便于解释举个例子，假设序列中A、B两个状态紧邻（排完序之后的），当前状态是从A状态转移过来的，那么它的长度自然和B状态一样，同时B状态的结尾字符是比当前状态大的（也有可能相等），那么根据我们第一步优化中的规则，B状态应该被当前状态替换掉；如果排完序之后发现没有一个已知状态可以转移，这个时候长度为1的状态应该被当前状态替换掉，因为当前状态的长度至少是1，而根据第一步优化中的规则，现在长度为1的状态的结尾字符比当前状态大，所以需要被替换掉

根据上一段的更新规则，我们可以惊奇地发现，更新完之后的序列依然是有序的，这可非常的amazing啊，因为这样我们就不用用sort进行排序了（降低总的时间复杂度），即我们的这种更新方式，不仅完成了数据更新，还顺便维护了当前的顺序，可以说是绝妙的更新方式

代码（y总原码）：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
//用一个数组来存储保留下的已知状态，下标表示子序列长度，对应下标存的内容是当前子序列长度中最小的结尾字符
int q[N];

int main()
{
    scanf("%d", &n);
    //这里y总是从下标0开始，上面举的例子是从1开始
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    //初始子序列长度为0（其实可以是1，原因看下一部分的分析）
    int len = 0;
    //下面是枚举每一个字符然后进行状态转移求解
    for (int i = 0; i < n; i ++ )
    {
        //二分找到最佳状态
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        //对应更新方式中的第一条，如果当前状态是从最后一个已知状态转移过来的r+1自然比len大1，max发挥作用
        len = max(len, r + 1);
        //对应更新方式中的后两条；对于更新方式中的第三条，因为l是从零开始的，所以如果没有一个已知状态可以转移，l=r=0，则r+1=1，长度为1的状态会被替换（所以l一定要从0开始）
        q[r + 1] = a[i];
        //因为更新完之后顺序不变，所以没有必要进行排序
    }

    printf("%d\n", len);

    return 0;
}

动态规划算法能够成立的大前提：

初始状态一定是已知的，通过将未知状态转移为已知状态，然后通过不断迭代的方式就能求出未知状态，其中最核心的就是状态转移的方式

大家会有这么一种感觉，就是我们上面说到的所有算法，都是基于我们已经得到了一个筛选完并且排好序的已知状态序列；很显然，这道题的初始状态是已知的，每个f至少是1（虽然代码里用不到但是分析需要），并且q[1]初始值应该是a[0]；也就是说我们确实可以得到一个筛选完并且已经排好序的已知状态序列，这也是上面那段话的意义所在

不信你拿下面的代码去试（我把初始状态补上去了），一样可以AC（y总代码里，当枚举的是a[0]时，二分其实不会执行，它会被直接放进q[1]，相当于初始化了q）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int len = 1;
    q[1]=a[0];
    for (int i = 1; i < n; i ++ )
    {
        int l =0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    printf("%d\n", len);

    return 0;
}

随着序列长度的增加，结尾字符也不断增大这个性质的证明：

这个证明其实很简单，使用反证法即可，为了便于描述，假设保留下的已知状态存在数组q里，其中q的下标表示长度，里面存的内容是该长度的子序列的最小结尾字符，则大前提是“长度为i的子序列的最小结尾字符是q[i]”，假设“长度为i+1的子序列的最小结尾字符q[i+1]比长度为i的子序列的最小结尾字符q[i]要小”成立，如果我们用这个结论推出了与大前提矛盾的结论则表明当前假设失败；根据最长上升子序列的要求，长度为i+1的子序列的倒数第二个字符x应该比q[i+1]要小，即x小于q[i]，而以x结尾的长度为i的子序列确实存在（不然就没有以q[i+1]结尾的长度为i+1的子序列了），如此长度为i的子序列的最小结尾字符应该是x而不是q[i]，与大前提矛盾，原假设不成立，即随着序列长度的增加，结尾字符也不断增大