Longest Increasing Subsequence revisited
Longest increasing subsequence is a famous example of dynamical programming[1, 2]. I’ll write about this problem in a slightly different point of view.
Increasing Triplet Subsequence
First we can discuss a related problem, which is called Increasing Triplet Subsequence[3]:
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Before solving this increasing triplet, how about solving a increasing couple problem. Increasing couple is simple, as the only case a array has not increasing couple is the array is absolutly decreasing. How about looking it at a different way. As a fact if we keep a record of the minimum element up to index i, then if the i+1 element is larger than this local minimum, the increasing couple is found.
If we call minimum element up to index i l_min[i], similarly we can define l_min2[i] as the minimum element up to index i, which is larger than at least one element with a smaller index. With the help of information from these two arrays, if nums[i+1] is larger than l_min2[i], an increasing triplet is found.
bool increasingTriplet1(vector<int>& nums) {
int len = nums.size();
if (len <= 2) return (0);
vector<int> l_min (len, INT_MAX);
vector<int> l_min2 (len, INT_MAX);
l_min[0] = nums[0];
for (int i = 1; i < len; i++) {
l_min[i] = min(l_min[i - 1], nums[i]);
}
for (int i = 1; i < len; i++) {
if (nums[i] > l_min[i - 1]) {
l_min2[i] = min(l_min2[i - 1], nums[i]);
} else {
l_min2[i] = l_min2[i - 1];
}
}
for (int i = 1; i < len; i++) {
if (nums[i] > l_min2[i - 1] &&
l_min2[i - 1] > l_min[i - 1]) {
return(true);
}
}
return(false);
}This is a standard dynamical programming example whose memory usage on storing tables could be optimized, here is the optimization:
bool increasingTriplet(vector<int>& nums) {
int len = nums.size(); if (len < 3) return(0);
int l_min = nums[0];
int l_min2 = INT_MAX;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > l_min2 ){
return(true);
} l_min = l_min < nums[i] ? l_min : nums[i]; if (nums[i] > l_min) {
l_min2 = min(l_min2, nums[i]);
}
} return(false);
}
Triplet Subsequence to k subsequence
This approach could be generalized to increasing k subsequence easily. We can define l_min, l_min2, l_min3, etc. Let’s start with an example with input:
[10, 9, 2, 5, 3, 7, 101, 18]local minimum will be updated as following
[10]
[9]
[2]
[2, 5]
[2, 3]
[2, 3, 7]
[2, 3, 7, 101]
[2, 3, 7, 18]We can see that there is at most one local minimum to be update for each new coming element, while the local minimum is an monotone increasing array. Here is an example using binary search implementation for finding the index of element in the local minimum to be update:
/*
* Given a monotone increasing sequence, find the
* minimum index whose value is larger or equal than
* new_num, return the length if the index does not
* exist.
*/
int
get_min_index(vector<int>& increasing_nums, int new_num){
int len = increasing_nums.size();
int left, right, mid;
if (len <= 0) {
return (0);
} else if (increasing_nums[len - 1] < new_num) {
return (len);
}
left = 0;
right = len - 1;
while(left + 1 < right) {
mid = left + (right - left) / 2;
if (increasing_nums[mid] < new_num) {
left = mid;
} else {
right = mid;
}
}
if (increasing_nums[left] >= new_num) {
return (left);
} else {
return (right);
}
}The largest k with a k-increasing subsequence is the answer to the LIS problem. Not only the length of the problem has been found, the actually subsequence is found at the same time. This is the so called “optimal” solution to the LIS problem.
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
vector<int> local_mins;
for (int i = 0; i < nums.size(); i++) {
update_local_mins(nums,local_mins,nums[i]);
}
return(local_mins.size());
}void update_local_mins(vector<int>& nums,
vector<int>& local_mins, int new_num){
int i = get_min_index(local_mins, new_num); if (i >= local_mins.size()) {
local_mins.push_back(new_num);
} else {
local_mins[i] = new_num;
}
}
More related thoughts
Another classical approach as example of dynamical programming If we define dp[i] as the maximal length of increasing subsequence which actually ends at index i, then there is an iterative condition:
dp[i] = (max{dp[j]} such that nums[j] < nums[i]) + 1 Translating to C++:
int lengthOfLIS1(vector<int>& nums) {
int len = nums.size(), res = 0;
vector<int> dp(len, 1); for (int i = 0; i < nums.size(); i++) {
for (int j = i - 1; j >=0; j--) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
} for (int i = 0; i < len; i++) {
res = max(res, dp[i]);
}
return(res);
}
The run time is 29ms comparing to 3ms for the “optimal” solution with the leetcode test samples. So the operations on updating seems not to be optimal, here we need a data structure supporting ordering and the above mentioned update.
More explicitly, if we look at (nums[i], dp[i]) as a pair in a plane, the update operation only needs getting max dp[i], whose nums[i] < new_num.
Potential candidates data structure for supporting this operation are monotone stack, segmentation tree, balanced binary tree and binary indexed tree.
Theses approaches will be added in new post.
