最长 上升子序列

大家好 我是寸铁 希望这篇题解对你有用，麻烦动动手指点个赞或关注，感谢您的关注

不清楚蓝桥杯考什么的点点下方👇

考点秘籍

想背纯享模版的伙伴们点点下方👇

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

蓝桥杯省一你一定不能错过的模板大全（第三期）

蓝桥杯省一你一定不能错过的模板大全（第四期）！！！

想背注释模版的伙伴们点点下方👇

蓝桥杯必背第一期

蓝桥杯必背第二期

往期精彩回顾

蓝桥杯上岸每日N题 第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

蓝桥杯上岸每日N题第一期(三)！！！

蓝桥杯上岸每日N题第二期(一)！！！

蓝桥杯上岸每日N题第三期(一)！！！

蓝桥杯上岸每日N题 第四期(最少刷题数)！！！

蓝桥杯上岸每日N题 第五期(山)！！！

蓝桥杯上岸每日N题 第六期(求阶乘)！！！

蓝桥杯上岸每日N题 第七期(小猫爬山)！！！

蓝桥杯上岸每日N题 第八期 (全球变暖)！！！

蓝桥杯每日N题 (消灭老鼠)

蓝桥杯每日N题（杨辉三角形）

操作系统期末题库 第九期(完结)

LeetCode Hot100 刷题(第三期)

idea创建SpringBoot项目报错解决方案

数据库SQL语句（期末冲刺）

想看JavaB组填空题的伙伴们点点下方 👇

填空题

竞赛干货

算法竞赛字符串常用操作大全

蓝桥杯上岸必刷！！！(模拟/枚举专题)

蓝桥杯上岸必背！！！ (第三期 DP)

蓝桥杯上岸必背！！！(第四期DFS)

蓝桥杯上岸必背！！！(第五期BFS)

蓝桥杯上岸必背！！！(第六期树与图的遍历)

蓝桥杯上岸必背！！！(第七期 最短路算法)

蓝桥杯上岸必背！！！(第八期 简单数论)

蓝桥杯上岸必刷！！！(进制、数位专题)

蓝桥杯上岸考点清单 (冲刺版）！！！

蓝桥杯上岸必背模板 (纯享版）

最长上升子序列

状态表示：

集合：所以**a[i]**为结尾的严格单调递增的子序列

属性：max

注：子序列的结尾必定是以某个数a[i]作为结尾，我们求出所有数作为结尾的子序列**，然后取一个max即可。

划分依据：最后一个不同的点

所有以a[i]为结尾的子序列，说明a[i]均相同，我们根据最后一个不同的点划分。

状态计算：

根据最后一个不同的点，可以将最后一个不同的点以**a[1]、a[2]、a[3]、…a[i-1]这几类进行划分，由于这几类划分标准的共同点均是以a[i]结尾，所以最后再加上a[i]这个点即可，即长度加1**。

得到状态转移方程如下：

$$f[i]=Math.max(f[i],f[j]+1)$$
特殊情况：只有a[i]自己一个数的时候，此时长度为1。这里需要在循环时进行特判，如果前面找不到比a[i]小的数，即a[j]>=a[i]时，则不需要更新长度。

为什么需要特判？

a[j]>a[i]:我们是以a[i]作为结尾的子序列,子序列严格递增,a[i]是最大的那个数。前面出现比a[i]大的数就不满足这一条件，不需更新长度。
a[j]=a[i]:当出现a[j]=a[i]时说明这两个数相同,我们只需要保留**a[i]这个数即可。即长度为1

Accode

import java.util.*;
public class Main{static int N=1010;static int a[]=new int[N];static int f[]=new int[N];public static void main(String []args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();for(int i=1;i<=n;i++)a[i]=sc.nextInt();for(int i=1;i<=n;i++){f[i]=1;//初始化每个i结尾的序列长度为1for(int j=1;j<i;j++){if(a[j]<a[i]){//特判一下//a[j]<a[i]需要更新//a[j]>=a[i]说明序列不合法f[i]=Math.max(f[i],f[j]+1);}}}long res=f[1];for(int i=1;i<=n;i++){res=Math.max(res,f[i]);}System.out.println(res);}
}