Longest Increasing Subsequence - Two Methods

In this post, I will explain the two approached to the classic problem: find the longest increasing subsequence of a given string. Besides, I will also introduce a similar problem, which is find the length of longest continuous increasing subsequence of a given string.

Problem statement

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Approach 1: dynamic programming

As we can see, this constraint is that increasing and this is a subsequence, no necessarily be a substring. It is obvious that it has overlapping subproblems. Where? Say you want to find the LIS of string s, you should firstly find the LIS of the substring(0, s.length() - 1), then try to append the last character to the previous subsequence. So, dp is a good candidate solution.

We can use a dp array to save the maximum LIS ends in each index. We try to get the maximum pre string LIS length, and then plus one. If the current number is greater its previous number, we update the maxPre. Finally, the LIS ends here, is that maxPre + 1. One case, is there is no less number preceding it, the result will be 1; the other case is, there is some numbers preceding it and less than it, so the result should definitely increment by 1.

The Time complexity is O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
dp[0] = 1;

int maxLen = 1;
for (int i = 1; i < n; i++) {
int maxPre = 0;
for (int pre = 0; pre < i; pre++) {
if (nums[i] > nums[pre]) {
maxPre = Math.max(maxPre, dp[pre]);
}
}

dp[i] = maxPre + 1;
maxLen = Math.max(dp[i], maxLen);
}

return maxLen;
}

Approach 2: Use TreeMap

The core idea is also try to append the current number to the previous subsequence. This time, we will use TreeMap, as TreeMap has a ceilingKey(i) method, so we can easily find whether the current number is the greatest number. If yes, we just increment by 1; if there is other key is greater than the current number, we update the key in the map.
The key of TreeMap is the number value, and the according value is the maximum LIS length ends here.

The time complexity is O(NlogN). As all the operations, remove(), put(), ceilingKey(i) is O(logN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
TreeMap<Integer, Integer> tmap = new TreeMap<>();
int maxLen = 1;
for (int i : nums) {
if (tmap.isEmpty()) {
tmap.put(i, maxLen);
} else {
Integer ceiling = tmap.ceilingKey(i);
if (ceiling == null) {
maxLen++;
tmap.put(i, maxLen);
} else {
int ceilingLen = tmap.get(ceiling);
tmap.remove(ceiling);
tmap.put(i, ceilingLen);
}
}
}

return maxLen;
}

Compared to Longest Continuous Increasing Subsequence

Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).

Example 1:

Input: [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is 3.
Even though [1,3,5,7] is also an increasing subsequence, it’s not a continuous one where 5 and 7 are separated by 4.

Example 2:

Input: [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2], its length is 1.

Solution

This problem is to find the longest length of increasing subarray.

Actually, we can solve this problem in linear time.

How? As this is subarray, once the current number is less or equal that its preceding number, the longest increasing subarray ends in this number will be 1. Otherwise, the maxLen increments by 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int maxLen = 1;
int len = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
len++;
maxLen = Math.max(maxLen, len);
} else {
len = 1;
}
}

return maxLen;
}