题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5f65ccbb025240bd8458eb6479c2612e
描述
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 ii 和 jj 满足 i<ji<j 且 arr_i \geq arr_jarri≥arrj。
数据范围： 0\leq n \leq 10000≤n≤1000 , |arr_i| \le 10^9 \∣arri∣≤109
要求：时间复杂度 O(n^2)O(n2)， 空间复杂度 O(n)O(n)
输入描述：
第一行输入一个正整数 n ，表示数组的长度
第二行输入 n 个整数表示数组的每个元素。
输出描述：
输出最长严格上升子序列的长度
示例1
输入：
7 6 3 1 5 2 3 7复制
输出：
4复制
说明：
该数组最长上升子序列为 [1,2,3,7] ，长度为4
解题思路：
1、定义dp[i]为以in[i]为结尾时的最长上升子序列的长度；
2、此时做选择，in[i]只能放入最长上升子序列，且in[i]放入后，其长度等于前i-1的上升子序列最大值+1
即in[i]>in[0...i-1]时
dp[i]=max(dp[0...i-1])+1;
in[i]<in[0...i-1]时
加入in[i]后的最长上升子序列只有其本身，故dp[i]=1；
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> in(n+1, 0);
for (int i = 0; i < n; i++) {
cin >> in[i+1];
}
vector<int> dp(n+1, 0); // dp[i]代表以in[i]做结尾时对于的最长上升子序列长度
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 0; j < i; j++) {
if (in[i] > in[j]) {
cnt = max(cnt, dp[j]);
}
}
dp[i] = cnt + 1;
}
sort(dp.begin(), dp.end());
cout << dp[n] << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
投递字节跳动等公司8个岗位
吓得我不敢去外包了，但是目前也只有外包这一个实习，我还要继续去吗