AcWing 蓝桥杯第十六届校内模拟赛 10. 最长上升子序列 * 2
原题链接
简单
作者:
JustDoIt11
,
2024-11-18 20:30:44
,
所有人可见
,
阅读 3
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i ++ )
arr[i] = sc.nextInt();
// 使用动态规划,让f[i]代表以arr[i]为结尾的最长下降子序列的长度
// 然后g[i]代表以arr[i]为起始的最长上升子序列的长度
int[] f = new int[n + 1];
int[] g = new int[n + 1];
for (int i = 1; i <= n; i ++ ) {
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (arr[i] < arr[j])
f[i] = Math.max(f[i], f[j] + 1);
}
for (int i = 1; i <= n; i ++ ) {
g[i] = 1;
for (int j = 1; j < i; j ++ )
if (arr[i] > arr[j])
g[i] = Math.max(g[i], g[j] + 1);
}
int ans = 0;
for (int i = 1; i <= n; i ++ )
if (f[i] > 1 && g[i] > 1)
ans = Math.max(ans, f[i] + g[i] - 1);
System.out.println(ans);
}
}