Let A be input array of size N and an auxiliary array minNumber, where minNumber[x] represents the smallest possible last element for LIS of length x of the observed array.

The idea behind the auxiliary array -

While iterating over A, we want to keep track of all the Increasing Sequence possible. Now, at any point in time, we will have multiple increasing sequences of length x but the one with smallest last value can generate sequences of length x+1 which will include all possible increasing sequences which can be generated by any other sequences of the same length. Also, we are not much concerned about the non-last element of all the increasing sequences while appending a new element. So we can just store the smallest possible last element for an increasing sequence of length x.

Note: minNumber will always be sorted.

Now assuming 1-based indexing, assigning manually for the first element -

  minNumber[1] = A[1];
  LIS = 1;

Now iterating over A, for the ith element. Let's say a = A[i] —

• If a is not more than minNumber[LIS], it is possible to reduce the last element of an existing length LIS. (Better minNumber)

• Else we can have a new Longest Increasing Subsequence observed till now.

Clubbing them together -

Binary search a in minNumber-

Find the largest value which is smaller than(or equal for nondecreasing sequences) a, and assign a at the next index of minNumber. If next index doesn't exists, insert a and increasing the LIS;

Finally, our solution will be value of LIS.

Some old snippet(Possibly working :p) -

int getLIS(vector<ll> &v) {
    ll N = v.size();
    vector<ll> smallest(N); //index = maxlen-1
    smallest[0]=v[0];
    int mxlen=1;
    for(int i=1;i<N;i++) {
        if(v[i]>smallest[mxlen-1]) {  // Change Here for nondecreasing
            smallest[mxlen++]=v[i]; 
        } else {
            int k=lower_bound(smallest.begin(),smallest.begin()+mxlen,v[i])-smallest.begin(); // Change Here for nondecreasing
            assert(k>=0 && k<mxlen);
            smallest[k]=v[i];
        }
    }
    return mxlen;  
}