有一次修改的LIS
作者:
不知名的fE
,
2025-02-03 12:18:13
,
所有人可见
,
阅读 1
import java.util.Scanner;
public class Main {
static final int N = 5010;
/*
f[i][0/1]为以i 结尾时是否修改的最长子序列
0:没有进行修改
1:进行了修改
明确最长上升子序列的求解原理:
子序列中的差分越小对序列的长度贡献越大(相比suf大的来说)
该题目的基本思路:LIS前后缀的拼接
状态转移
初始f[1] = {1, 1}
if (a[j] < a[i]) => j=[1, j)
f[i][0] = max(f[j][0] + 1)//不修改
f[i][1] = max(f[j][1] + 1)//在前面的区间修改
if (可以插入值)//修改i和j中间的一个值缩小差值(修改当前区间),长度+2
f[i][1] = max(f[j][0] + 2)
这样会出现两个边界问题
1. a[1]是不会修改的:1前面没有前缀
根据f[1][1] = max(f[j][0] + 2) => j=[1, i)
由此发现将j的左边界变成0并需要满足if条件即可即j=[0, j),a[0]=-1
2. a[n]是不会修改的:n后面没有后缀
在最后枚举一下即可
//在第i个位置接上第n个位置修改值
for (int i = 1; i < n; i++) {
ans = Math.max(ans, f[i][0] + 1);
}
*/
static int[][] f = new int[N][2];
static int[] a = new int[N];
static int n;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
int ans = 0;
a[0] = -1;
for (int i = 1; i <= n; i++) {
f[i] = new int[]{1, 1};
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
f[i][0] = Math.max(f[i][0], f[j][0] + 1);
f[i][1] = Math.max(f[i][1], f[j][1] + 1);
if (i - j > 1 && a[i] - a[j] > 1) {//有一个中间数值
f[i][1] = Math.max(f[i][1], f[j][0] + 2);
}
}
}
ans = Math.max(ans, Math.max(f[i][0], f[i][1]));
}
for (int i = 1; i < n; i++) {
ans = Math.max(ans, f[i][0] + 1);
}
System.out.println(ans);
}
}