// This is a pure dynamic programing approach which takes O(n^2) time
int LIS(vector<int> &ar, int n)
{

    int dp[n]; // creating dp array
    int ans = dp[0] = 1;

    for (int i = 1; i < n; i++)
    {
        int maxi = 0;

        // traversing for all previous elements
        for (int j = 0; j < i; j++)
        {
            if (ar[i] > ar[j])
            {
                maxi = max(maxi, dp[j]);
            }

            dp[i] = 1 + maxi;

            // here answer is the largest value from dp array
            ans = max(ans, dp[i]);
        }
    }

    return ans;
}