This is a standard problem which is solved using Dynamic Programming. To get the intuition of DP, first let us consider the recursive approach.
Approach 1: Recursion + Memoization
// memo[i][j] stores longest increasing subsequence from i...j
int lengthOfLIS(vector<int> &nums) {
int n = nums.size();
nums.push_back(INT_MIN);
vector<vector<int>> memo (n + 1, vector<int>(n, -1));
return helper(nums, n, 0, memo);
}
int helper(vector<int> &nums, int loIndex, int pos, vector<vector<int>> &memo) {
if (pos >= nums.size() - 1) return 0;
if (memo[loIndex][pos] != -1) return memo[loIndex][pos];
int x = 0;
if (nums[pos] > nums[loIndex]) // consider nums[pos] as part of sequence
x = 1 + helper(nums, pos, pos + 1, memo);
int y = helper(nums, loIndex, pos + 1, memo); // do not consider nums[pos] as part of sequence
return memo[loIndex][pos] = max(x, y);
}
Approach 2: Dynamic Programming
// dp[i] stores length of longest increasing subsequence ending at index i
int lengthOfLIS(vector<int>& nums) {
if(!nums.size())
return 0;
vector<int> dp(nums.size(), 1);
int maxLen = 1;
for (int i=1; i<nums.size(); i++) {
for (int j=0; j<i; j++) {
if (nums[j]<nums[i])
dp[i] = max(dp[i], dp[j]+1);
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}