算法之最长递增子序列

偏执的太偏执、 2022-07-21 00:05 169阅读 0赞

一、求序列的最长递增子序列长度。构造递归方程，求最优解的值，即最长递增子序列的长度。![Image 1][]

![Center][]

上述F（i）是以ai结束的最长递增子序列的长度，在所有的F（i）中选最大的，就是整个序列的最长递增子序列长度。以上算法时间复杂度为O(n\*n).

二、这个跟上面思路的是一样的，不过是比较详细，加了构造最优解的过程。

1，求最长递增子序列长度。

求解以a\[i\]为末元素的最长递增子序列时，首先、找到所有序号在a\[i\]前面且小于a\[i\]的元素a\[j\]，即j<i且a\[j\]<a\[i\]。

如果这样的元素存在，那么对于a\[j\],都有一个以a\[j\]为末元素的最长递增子序列，长度设为p\[j\]，把其中最大的p\[j\]选出来，那么p\[i\]就等于最大的p\[j\]加1，即以a\[i\]为末元素的最长递增子序列，等于以使p\[j\]最大的那个a\[j\]为末元素的递增子序列最末再加上a\[i\]；

如果这样的元素不存在，那么a\[i\]自身构成一个长度为1的以a\[i\]为末元素的递增子序列。

最后在数组p\[i\]中找到最大的那个长度。

以下为求最长递增子序列长度的代码其中p\[i\]为以a\[i\]为末元素的最长递增子序列长度，q\[i\] 为以a\[i\]为末元素的最长递增子序列的a\[i\]前面一个点a\[j\]的序号，k为序列中最长公共子序列的长度，l为序列中最长公共子序列末元素位置。

![Center 1][]

2,构造最优解。

由于有p\[i\]为以a\[i\]为末元素的最长递增子序列长度，q\[i\] 为以a\[i\]为末元素的最长递增子序列的a\[i\]前面一个点a\[j\]的序号，k为序列中最长公共子序列的长度，l为序列中最长公共子序列末元素位置。 我们可以根据k与l确定最长公共子序列长度和末元素，根据q\[i\]依次找到最长公共子序列的前一个元素，直到p\[i\]为1时即构造出最长递增子序列。   
以下为构造最长递增子序列的代码,输出以i那个位置的元素结束的最长公共子序列，要求整个序列的最长递增子序列，给i传上面求得的l即可。

![Center 2][]

三、改进为O(nlogn).

在方案二的这个算法中“首先、找到所有序号在a\[i\]前面且小于a\[i\]的元素a\[j\]，即j<i且a\[j\]<a\[i\]。”的实现是通过扫描a\[i\]前面的所有数据而得，这就使得每次循环的时间复杂度达到O(n)，而循环次数为n，总的时间复杂度为O(n2)。

循环次数无法改变的情况下，可以考虑改进扫描算法。因为a\[i\]值的无序性难以更改，这就需要寻找一个标准在不增加额外操作的情况下对a\[i\]排序的方法。对a\[i\]前的序列a\[1\]到a\[i-1\]看作一个排好序的序列F，F的小标为a\[1\]到a\[i-1\]的值，每次循环查询a\[1\]到a\[i-1\]时，把他看作是查询F，F是按照A的值排序的，对F使用二分查找，可以使得每次查询的代价在O(lgi)，使得总的时间复杂度为O(nlgn)。

虽然，此种方法可以解决求解最长递增子序列的长度，但是这使得方案二中“p\[i\]为以a\[i\]为末元素的最长递增子序列长度，q\[i\] 为以a\[i\]为末元素的最长递增子序列的a\[i\]前面一个点a\[j\]的序号”中的q\[i\]无法得出，使得标准的迭代输出最长递增子序列的方式无法实现，这就需要另一种方案来实现构造最长递增子序列，且他的时间复杂度不可以超过O(nlgn)。这部分整理自http://wenku.baidu.com/link?url=a-DbiXLMO5vbKXFAULZPdll\_xGO0TuXCnkVJfZsNgeYpL3EHE2IfrPU0xe7X0K6UV9sUIyBarjUHIQB0jYmX-DMADEmqOPJBDrU4lMm62bG

其中的构造最长递增子序列，且时间复杂度不可以超过O(nlgn)的部分没看明白。

[Image 1]: 
[Center]: /images/20220720/4fc9e7fd284c4c27bcb86dab75c6005c.png
[Center 1]: /images/20220720/a2dc6825ca5e4e41adb54ab4d3a4be4b.png
[Center 2]: /images/20220720/0ba25ee76af3467caafa0e47e300c6b9.png