最长上升子序列（c++图文详解）

这题思路是这样，假设这个序列长度为n，存在数组a中，maxlen[i]表示以第i个数为终点的最长上升子序列的长度，它被初始化为1，因为一开始单个字符的最长上升子序列都是1（它自己），我们先用一个循环i遍历这个序列，i从2（序列的第2个字符）开始一直加1加到n，表示求以第i个数为终点的最长上升子序列的长度，然后同时在这个循环下再来一个循环j，j从1开始加1一直加到i-1为止，表示以第j个数为终点的最长上升子序列。只要出现a[i]>a[j]的情况，maxlen[i]=max(maxlen[i],maxlen[j]+1),首先看maxlen[j]+1,因为a[i]>a[j]了，说明以第j个数为终点的最长上升子序列后面又多了一位比这个最长上升子序列大的，也就是a[i]，这个序列变成以a[i]为终点的了，所以长度要加1，注意j的范围是（1,i-1）,所以以第i个数为终点的最长上升子序列的长度至少是maxlen[j]+1,再跟maxlen[i]比较，因为maxlen[i]通过更新是有可能比maxlen[j]+1大的。
我们用图来表示这个解法，以题目例

最长上升子序列（c++图文详解）最先出现在Python成神之路。