设计一个o(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

### 回答1：
这里是一个O(n^2)时间复杂度的动态规划算法，用于找出长度为n的序列中的最长单调递增子序列。

定义一个长度为n的数组dp，其中dp[i]表示以序列中第i个元素结尾的最长递增子序列的长度。初始时，将dp数组的所有值都初始化为1，因为最长递增子序列至少包含自己一个元素。

然后，我们可以使用两个嵌套循环来遍历序列中的所有元素，使用一个指针j来指向当前元素之前的所有元素，检查dp[j]是否小于dp[i]，且第j个元素小于第i个元素，如果是这样，那么我们可以更新dp[i]为dp[j]+1，因为这意味着我们可以在以j结尾的最长递增子序列的末尾添加第i个元素。

最终，最长递增子序列的长度就是dp数组中的最大值。

下面是算法的Python代码实现：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

这个算法的时间复杂度为O(n^2)，因为我们使用了两个嵌套循环来遍历整个序列，对于每个元素，我们需要比较它之前的所有元素，这需要O(n)的时间复杂度，因此总时间复杂度为O(n^2)。

### 回答2：
最长单调递增子序列问题，是指在一个无序序列中寻找一个子序列，使得这个子序列的元素是递增的，且这个子序列的长度尽可能地长。设原始序列长度为n，则最长单调递增子序列的长度为m（1≤m≤n）。

一般来说，我们可以使用一个dp数组来进行状态转移。其中dp[i]表示以第i个元素为结尾的最长单调上升子序列的长度。初始状态时，dp[i]都应该为1，因为每个元素本身就构成一个长度为1的上升子序列。

在状态转移中，需要判断在前i-1个元素中是否存在比第i个元素更小的元素j，如果存在，则dp[i]可以由dp[j]转移得到（加一个1）。

因为需要比较前i-1个元素，所以最基本的暴力方法时间复杂度为O(n^2)。具体来说，可以使用两层嵌套循环，第一层枚举以哪个元素为结尾，第二层枚举前i-1个元素中的最后一个元素，看是否小于第i个元素。

以下是伪代码：

初始化：dp[i] = 1，其中 1≤i≤n
for i in (1,n) do
for j in (1,i-1) do
if a[j] < a[i] then
dp[i] = max(dp[i], dp[j]+1)

实际上，我们还可以结合一些技巧来进行优化，把时间复杂度进一步降低为O(nlogn)。这需要借助其他算法，例如二分查找和贪心思想。因为这些技巧已经超过题目所限，本回答不再深入探讨。

### 回答3：
问题描述：

有一个由n个数字组成的序列，求该序列的最长单调递增子序列。

解决方案：

此问题的最优解已知是 O(nlogn) 时间复杂度，使用动态规划和二分查找。

本文介绍一个 O(n^2) 时间的动态规划算法。

算法基本思路：

首先定义 dp[i] 为以第 i 个数字为结尾的最长单调递增子序列长度。初始值都为 1，即每个数字本身都是一个长度为1的递增子序列。

接着，从序列第二个数字开始遍历，枚举其前面每一个数字 j，如果该数字比当前数字小则说明它可以接在 j 后面形成一个更长的递增子序列，此时可以将 dp[i] 更新为 dp[j]+1。依次遍历，找出所有以 i 结尾的递增子序列中最长的长度，即为答案。

算法伪代码：

1. 定义 dp[i] 为以第 i 个数字为结尾的最长单调递增子序列长度，初始值都为 1
2. 从第二个数字开始遍历，枚举当前数字 i
a. 依次枚举 i 前面的数字 j，如果 nums[i]>nums[j] 则更新 dp[i]=dp[j]+1
3. 遍历 dp 数组，找出其中最大的长度，即为答案

算法复杂度：

时间复杂度：O(n^2)，需要遍历序列中的每个数字，并依次枚举其前面的数字，所以时间复杂度是 O(n^2)。

空间复杂度：O(n)，需要存储 dp 数组。

参考代码（Python）：

def LIS(nums):
n = len(nums)
dp = [1 for _ in range(n)]
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)

nums = [10,9,2,5,3,7,101,18]
print(LIS(nums)) # expect 4