Longest Increasing Subsequence (Dynamic Programming)

Program:-

// Note: set(stl c++) don't use if the input are not distinct... 

#include <bits/stdc++.h>
using namespace std;

class Lis{
    int size;
    public:
    int *arr;
    Lis(int n){
        size=n;
        arr=(int *)malloc(sizeof(int)*n); 
//arr=new int(n);  See the miracle to uncomment it and comment malloc funtion;
    }
    void input();
    int Lislength();
};

void Lis::input(){
    for(int i=0;i<size;i++) cin>>arr[i];
}

int Lis::Lislength(){
    int j;
    vector<int>vec;
    vec.push_back(arr[0]);
    for(int i=1;i<size;i++)
    {
        for( j=0;j<vec.size();j++)
        {
            if(arr[i]<=vec[j])
            {
                vec[j]=arr[i];
                break;
            }
        }
        if(j==vec.size())
        vec.push_back(arr[i]);
    }
    return vec.size();
}

int main()
{
    int n;
    cin>>n;
    Lis lis(n);
    lis.input();
    cout<<lis.Lislength();
    return 0;
}