「线性DP-步入」最长上升子序列（LIS）

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

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

输出格式

输出一个整数，表示最大长度。

数据范围

$1\le N\le 1000$
−109≤数列中的数≤109−10^9≤数列中的数≤10^9−109≤数列中的数≤109

https://www.acwing.com/problem/content/description/897/

输入输出样例

7
3 1 2 1 8 5 6

4

分析

来看看样例的序列 3 1 2 1 8 5 6，所求得的最长上升子序列为 1 2 5 6，即为 4。
先假设 dp(i) 定义：表示前 i 个序列的最长上升子序列。
但此时会有一个问题，我们无法确定最后一个元素的位置到底在哪，只有确定了最后一个元素的位置我们才可以向前推，因为前面所要选的元素一定比后面的小。
此时定义更改为：表示前 i 个序列的最长上升子序列，并且第 i 个元素必须要选。

• 原问题：求最长上升子序列
• 子问题：求前 i 个元素的上升子序列
• DP 定义：表示前 i 个序列的最长上升子序列，并且第 i 个元素必须要选。
• DP 方程：dp[i]=max{dp[j]+1}（j<i）dp[i] = max\\{dp[j] + 1\\}（j < i）dp[i]=max{dp[j]+1}（j<i）

代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), ans = 0;int[] A = new int[1005];int[] B = new int[1005];for(int i = 1; i <= n; i++) {A[i] = sc.nextInt();B[i] = 1;}for(int i = 2; i <= n; i++) {for(int j = 1; j < i; j++) {if(A[i] > A[j]) {B[i] = Math.max(B[j] + 1, B[i]);}}ans = Math.max(ans, B[i]);}System.out.println(ans);}
}