Wavio 序列 - UVa - LIS-nLogn

Question

我正在尝试解决 uva 的问题 10534。问题很简单，即

1. 在数组 L1[].
中的每个索引 i 存储 LIS
2. 反转输入数组nums[]。
3. 将此反向数组 nums[] 的 LIS 存储在 L2[]
中
4. 反转L2[].
5. 现在 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;
        }
    }
}

Answer 1

不确定您的输入法是否适合 uva 解决方案...

试试这个：

public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] nums = new int[n];
            for(int i=0; i<n; ++i) nums[i] = in.nextInt();
            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;
        }
    }