最长递增子序列 给出长度为n的数组,找出这个数组的最长递增子序列。 (递增子序列

最长递增子序列（Longest Increasing Subsequence，简称LIS）是一个经典的问题，在计算机科学和数学等领域都有广泛的应用。下面是求解最长递增子序列的一种动态规划算法：

假设给定的数组为a[0...n-1]。我们可以定义一个长度为n的数组dp，其中dp[i]表示以a[i]结尾的最长递增子序列的长度。显然，dp[0] = 1，因为以a[0]结尾的最长递增子序列只有一个元素a[0]。

对于任意的i（1 <= i < n），以a[i]结尾的最长递增子序列可以通过从前面的元素中选择一个小于a[i]的元素，并将其接在以该元素结尾的最长递增子序列的后面得到。因此，可以使用一个嵌套的循环来搜索前面的元素，并计算以a[i]结尾的最长递增子序列的长度：

for i = 1 to n-1 do
dp[i] = 1
for j = 0 to i-1 do
if a[j] < a[i] and dp[j]+1 > dp[i] then
dp[i] = dp[j]+1

在上面的算法中，第二层循环用于搜索前面的元素，如果找到一个小于a[i]的元素j，并且以a[j]结尾的最长递增子序列的长度加上1大于以a[i]结尾的最长递增子序列的长度，则更新dp[i]的值。

最终，最长递增子序列的长度就是dp数组中的最大值。需要注意的是，这个算法的时间复杂度为O(n^2)，可以通过使用二分查找优化到O(nlogn)。