Longest Increasing Sub-sequence (DP-15)

You are given an array of non-negative integers. You need to find the length of the longest subsequence which has all the elements sorted in increasing order.

Sample Input: { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
Expected Output: 6
Explanation: One possible subsequence is { 0, 4, 6, 9, 13, 15 }

Algorithm:

The problem can be solved using dynamic programming as it has both optimal substructure and overlapping subproblem.

  1. We create an array DP to store the result of the subproblems. DP [i] will store the length of the longest increasing subsequence upto i’th element of the given array.
  2. We initialize DP [0] with 1 and all other cells with 0.
  3. We iterate for every position in DP array and do the following for each iteration. For each cell, we visit all the previous indices and check whether any index has element less than the current element and the answer for that subproblem stored in DP array is greater than the current value in DP array. If so, we update the current index in DP array, with the value in that particular index. After visiting all the previous cells, we add 1 to the final value which will make sure we include the current element as well.
  4. Finally, we return the maximum value in the DP array.
#include <bits/stdc++.h>
using namespace std;

int lis(vector<int> nums){
	int n = nums.size();
	vector<int> dp(n, 0);
	dp[0]=1;
	for(int i=1; i<n; i++){
		for(int j=0; j<i; j++){
			if(nums[j]<nums[i] && dp[j]>dp[i]){
				dp[i]=dp[j];
			}
		}
		dp[i]+=1;
	}
	return *max_element(dp.begin(), dp.end());
}

int main(){
	vector<int> nums = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
	cout<<lis(nums);
	return 0;
}

Also, check out another popular interview problem Minimum Path Sum.

2 comments

Leave a Reply

Your email address will not be published.