CODEWITHSUNDEEP
javaalgorithm
Sanku
Sanku

Reputation: 511

Longest Increasing SubSequence using Binary Search

I am trying to implement The Longest Increasing SubSequence using Binary Search. Well I have coded the algorithm and my test cases are getting satisfied but when I submit the code,it is failing for some test cases like for example for the following list,

29471 5242 21175 28931 2889 7275 19159 21773 1325 6901, the answer should be 4 but I am getting 5.Below is my code,

import java.util.Scanner;

public class LongestIncreasingSubSequence {

    public static int BS(int[] arr,int low,int high,int key){

        int mid;

        while ((high - low) > 1) {

            mid = (int) Math.ceil((low + high) / 2);

            if (arr[mid] >= key) {
                high = mid;
            } else {
                low = mid;
            }
        }
        return high;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n;
        n = sc.nextInt();
        int arr[] = new int[n];
        int LS[] = new int[arr.length];
        int count = 1;

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        LS[0] = arr[0];

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < LS[0]) {
                LS[0] = arr[i];
            } else if (arr[i] > LS[count-1]) {
                LS[count++] = arr[i];
            } else {
                LS[BS(arr,0,count-1,arr[i])] = arr[i];
            }
        }
        System.out.println(count);
    }
}

So can anyone please tell me where I am going wrong.Thanks in advance.

Upvotes: 3

Views: 586

Answers (1)

kraskevich
kraskevich

Reputation: 18576

There is a bug here:
LS[BS(arr,0,count-1,arr[i])] = arr[i];should be
LS[BS(LS,0,count-1,arr[i])] = arr[i]; instead, because we need to update the array with the smallest value for each length of an increasing sub sequence (that is, LS), not the original one. With this change, it works properly on your test case (I haven't tested it on anything else, but the algorithm looks correct to me now).

Upvotes: 1

Related Questions