我正在尝试解决 uva 的问题10534。问题很简单,即
- 将 LIS 存储在数组中的每个索引 i 处
L1[]
。 - 反转输入数组
nums[]
。 - 将此反向数组的 LIS 存储
nums[]
在L2[]
- 反向
L2[]
。 - 现在
L2[]
从右侧而不是左侧表示索引 i 处的 LIS。
我通过了示例测试用例,但每次提交时都会出现运行时错误。谁能解释这是为什么?我需要在哪里更改我的代码。
class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true){
String s = br.readLine();
if(s == null || s.equals("")) break;
int n = Integer.parseInt(s);
int[] nums = new int[n];
String[] str = br.readLine().split(" ");
for(int i=0; i<n; ++i) nums[i] = Integer.parseInt(str[i]);
int[] L1 = new int[n];
/**L1[] represents LIS ending at i**/
LIS(nums,n,L1);
/**reverse nums to find LIS*/
reverse(nums);
/**L2[] represents LIS on reverse of nums*/
int[] L2 = new int[n];
LIS(nums,n,L2);
/**L2[] represents LIS ending at i starting from right to left*/
reverse(L2);
int ans = 0;
for(int i=0; i<n; ++i){
ans = Math.max(ans, Math.min(L1[i],L2[i]));
}
System.out.println(2*ans-1);
}
}
public static void LIS(int[] nums,int n, int[] L1){
int[] I = new int[n+1];
Arrays.fill(I, Integer.MAX_VALUE);
I[0] = Integer.MIN_VALUE;
for(int i=0; i<n; ++i){
int l=0,r=n;
while(l <= r){
int mid = l + (r-l)/2;
if(I[mid] < nums[i])
l = mid+1;
else
r = mid-1;
}
I[l] = nums[i];
L1[i] = l;
}
}
public static void reverse(int[] L){
int l=0;
int r=L.length-1;
while(l < r){
int temp = L[l];
L[l++] = L[r];
L[r--] = temp;
}
}
}