LIS || PEC005

HelloooO!!! to all Visitors!!!
PROBLEM
I am getting some sort of infinite loop in codechef and wrong answer. I dont understand WHYYYYYYY!. Is there any Great Human Who Could HELP ME?
Thanks

#include <bits/stdc++.h>
using namespace std;
int lis(int a[],int n){

    if(n==0){
        return 0;
    }
    int min_last[n]={0};
    int len = 1;
    min_last[0]=a[0];
    for(int i=1;i<n;++i){
        auto lb = lower_bound(min_last,min_last+len,a[i]); // gives us pointer of that position

        if(lb==min_last+len)
            min_last[len++] = a[i];
        else
            *lb = a[i];

    }
    return len;

}

int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        int a[n];
        for(int i=0;i<n;++i){
            cin>>a[i];
        }
        cout<<lis(a,n)<<"\n";


    }







    return 0;
}

Consider this test case

Input

1
6
9 1 6 1 3 7 

Expected Output

4

Your Output

3

Explanation

Longest non-decreasing subsequence: 1 1 3 7

1 Like

Oh :- what can i do to solve i cant figure out

I have No Idea. :frowning:

[Works only for this problem since the limits are less]

Ever came across Longest common subsequence?

Ah, No Actually I am too MUCH CONFUSED. Even Getting LIS into my brain took me 2days!

Um… What would be the pre-requisties?

Refer to the following for a better understanding

Approach (based on the above resources):

  • Let B = sorted(A)
  • Find the length of the longest common subsequence of A and B (also think why it works).

Ok thanks. I would hit back after installing those information into memory