Wavio序列- UVa - LIS-nLogn

Question

我正试图解决uva的问题10534。这个问题是直截了当的。

1. 将LIS存储在数组L1[]中的每个索引I中。
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;
        }
    }