// 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; }