最长上升子序列 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。 时间限制：11000 内存限制：65536 输入 输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 输出 最长上升子序列的长度。 样例输入 7 1 7 3 5 9 4 8 样例输出 4 c++程序

#include <iostream>
#include <vector>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
int maxLen = 1;

for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}

return maxLen;
}

int main() {
int n;
cin >> n;

vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}

int result = longestIncreasingSubsequence(nums);
cout << result << endl;

return 0;
}

相关问题

一个数的序列bi，当b1<b2<...<bs的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,an)，我们可以得到一些上升的子序列(ai1,ai2,...,aik)，这里1≤i1<i2<...<ik≤n。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。 你的任务，就是对于给定的序列，求出最长上升子序列的长度。

题目描述：给定一个序列，求其最长上升子序列的长度。

解题思路：动态规划

设dp[i]表示以第i个数结尾的最长上升子序列的长度，则有：

dp[i] = max{dp[j]+1} (1<=j<i, aj<ai)

即在前i-1个数中，找到一个数j，使得aj<ai，并且dp[j]+1最大，那么dp[i]就等于dp[j]+1。

最终的答案就是dp数组中的最大值。

时间复杂度：O(n^2)

代码实现：

给定一个无序的整数数组，找到其中最长上升子序列的长度

这个问题可以使用动态规划来解决。

我们可以定义一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。初始化 dp 数组的所有元素为 1，因为每个元素本身都可以作为一个长度为 1 的上升子序列。

接下来，我们可以通过两个嵌套的循环来遍历数组 nums。对于每个位置 i，我们可以遍历它之前的所有位置 j (j < i)，如果 nums[j] 小于 nums[i]，则可以将 nums[i] 加入到以 nums[j] 结尾的最长上升子序列中，从而得到一个以 nums[i] 结尾的更长的上升子序列。因此，我们可以更新 dp[i] 为 dp[j] + 1 和当前 dp[i] 中的较大值。

最后，我们可以遍历 dp 数组，并返回其中的最大值，即为整个数组 nums 的最长上升子序列的长度。

以下是 Python 代码实现：

def lengthOfLIS(nums):
    n = len(nums)
    if n == 0:
        return 0

    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)$。