Longest increasing subsequence technique (dynamic programming)
Aleksei
1421
Dynamic ProgrammingCCareer

Dynamic programming is a big topic and I would like to talk about one technique: logest increasing subsequence or LIS.

Note: If you would like to see more posts about dynamic programming with this type of explanation/problem variants and list to practise please up-vote.

Longest Increasing Subsequence
As a paragraph states, the problem Longest Increasing Subsequence is to find a longest increasing subsequence in the input array and can be solved like:

vector dp(nums.size(), 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[j] + 1, dp[i]);
	}
}
return *max_element(dp.begin(), dp.end());

The idea is that dp[i] will represent the longest increasing subsequence until that point. Initially the length of LIS for each element is 1. To find the next longest increasing subsequence we will use previous calculated value from the dp array.
In this specific case this algorithm can be improved by using binary search lower_bound() :

vector<int> dp;
for (auto& n : nums) {
	auto it = lower_bound(dp.begin(), dp.end(), n);
	if (it == dp.end()) dp.push_back(n);
	else *it = n;
}
return dp.size();

In the second example dp will represent the longest increasing subsequence itself. We will try to find a value that is greater or equal than current value n. If there is no such value we will insert it into the array. Otherwise we will replace it with current value n.

Another problem Largest Divisible Subset is helpful to solve because it introduces how to restore the real longest increasing subsequence:

vector largestDivisibleSubset(vector& nums) {
	std::sort(nums.begin(), nums.end()); // Is needed because of this specifi problem, please check the explanation in the solution under this problem.
	vector dp(nums.size(), 1);
	vector prev(nums.size(), -1); // We will use extra array to track previous index.
	int maxind = 0;
	for (int i = 1; i < nums.size(); i++) {  // The same LIS algorithm.
		for (int j = 0; j < i; j++) {
			if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
				prev[i] = j; // One alteration of algorithm: we store previous index from where we came.
			}
		}
		if (dp[i] > dp[maxind]) maxind = i; // Store the largest index to restore the sequence later.
	}
	vector<int> res;
	while (maxind != -1) { // Restore the result.
		res.push_back(nums[maxind]);
		maxind = prev[maxind];
	}
	reverse(res.begin(), res.end());
	return res;
}

Key points to take away from the above two examples:

// The LIS algorithm itself
for (int i = 1; i < nums.size(); i++) {
	for (int j = 0; j < i; j++) {
		if (...) {
			dp[i] = dp[j] + 1;
			prev[i] = j;  // Using auxiliary array to track the previous indexes.
		}
	}
}
// Restoring the subsequence itself.
while (maxind != -1) {
	res.push_back(nums[maxind]);
	maxind = prev[maxind];
}
// Improvement that can be helpful sometimes by using binary search.
for (auto& n : nums) {
	auto it = lower_bound(dp.begin(), dp.end(), n); // or upper_bound() depending on problem statement.
	if (it == dp.end()) dp.push_back(n);
	else *it = n;
}

Problems to practice:

  1. Longest Increasing Subsequence: https://leetcode.com/problems/longest-increasing-subsequence/
  2. Largest Divisible Subset: https://leetcode.com/problems/largest-divisible-subset/
  3. Longest String Chain: https://leetcode.com/problems/longest-string-chain/
  4. Number of Longest Increasing Subsequence: https://leetcode.com/problems/number-of-longest-increasing-subsequence/
  5. Find the Longest Valid Obstacle Course at Each Position (4th problem in WeeklyContest253): https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/

I believe that you noticed words Longest/Largest in the problem name, so it can ring a bell that this problem might be be solved using LIS patern.

Comments (1)