P1309 最长单调递增子序列

题目描述

给出一个长度为n的序列，请找出最长的不下降子序列。（若有多个答案，请输出其中字典序最小的）。

输入格式

第一行包含整数n。

第二行包含n个整数，表示整个序列。

输出格式

第一行包含整数m，表示最长不下降子序列的长度。

第二行包含m个整数，表示最长不下降子序列。

数据范围

1≤n≤1000，1≤序列中的数≤10000

输入样例：

5
3 1 4 2 5

输出样例：

3
3 4 5

算法

(动态规划) $O(n^2)$

时间复杂度

状态数O(n),状态转移O(n),总时间复杂度O(n^2)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
vector<int> LIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
vector<vector<int>> path(nums.size());
dp[0] = 1;
path[0].push_back(nums[0]);
int max_length = 1, max_pos = 0;
for (int i = 1; i < nums.size(); i++) {
int max_dp = 1, max_j = -1;
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && dp[j] + 1 > max_dp) {
max_dp = dp[j] + 1;
max_j = j;
}
}
dp[i] = max_dp;
if (max_j != -1) {
path[i] = path[max_j];
}
path[i].push_back(nums[i]);
if (dp[i] > max_length) {
max_length = dp[i];
max_pos = i;
}
}
return path[max_pos];
}
};