A very common problem in computer programming is finding the longest increasing (decreasing) subsequence in a sequence of numbers (usually integers). Actually this is a typical dynamic programming problem.
We need to find maximum increasing subsequence length. In the brute-force approach, we can model this problem as -
If the current element is greater than the previous element, then we can either pick it or dont pick it because we may get a smaller element somewhere ahead which is greater than previous and picking that would be optimal. So we try both options.
If the current element is smaller or equal to previous element, it can’t be picked.
publicclassSolution {
publicintlengthOfLIS(int[] nums) {
return dfs(nums, 0, Integer.MIN_VALUE);
}
privateintdfs(int[] nums, int idx, int prev) {
if (idx == nums.length) {
return 0;
}
int pick = 0;
if (nums[idx]> prev) {
// we pick curr element as it is more than prev for now pick = 1 + dfs(nums, idx + 1, nums[idx]);
}
// this time we dont pick the element// 0 indicates length will not be updatedint dontPick = 0 + dfs(nums, idx + 1, prev);
return Math.max(pick, dontPick);
}
}
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
@lru_cache(None) # Memoization decoratordefdfs(idx: int, prev: int) -> int:
# Base condition: when we reach the end of the arrayif idx == len(nums):
return0# Option 1: Pick the current element if it's greater than prev pick =0if nums[idx] > prev:
pick =1+ dfs(idx +1, nums[idx])
# Option 2: Skip the current element dont_pick = dfs(idx +1, prev)
# Return the maximum of both optionsreturn max(pick, dont_pick)
# Start recursion with initial valuesreturn dfs(0, float('-inf'))
There are many unnecessary repeated calculations in the brute-force approach. We can observe that the length of increasing subsequence starting atĀ ith element with previously picked elementĀ prevĀ will always be the same. So we can useĀ dynamic programmingĀ to store the results for this state and reuse again in the future.
publicclassSolution {
publicintlengthOfLIS(int[] nums) {
return dfs(nums, 0, Integer.MIN_VALUE, new HashMap<>());
}
privateintdfs(int[] nums, int idx, int prev, Map<String, Integer> memo) {
// Base condition: when we go beyond the array, return 0if (idx == nums.length) {
return 0;
}
// Create a unique key for the current state String key = idx +","+ prev;
// Check if the result for this state is already computedif (memo.containsKey(key)) {
return memo.get(key);
}
// Option 1: Pick the current element if it's greater than prevint pick = 0;
if (nums[idx]> prev) {
pick = 1 + dfs(nums, idx + 1, nums[idx], memo);
}
// Option 2: Skip the current elementint dontPick = dfs(nums, idx + 1, prev, memo);
// Compute and store the result in the memo tableint result = Math.max(pick, dontPick);
memo.put(key, result);
return result;
}
}
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
@lru_cache(None) # Memoization decoratordefdfs(idx: int, prev: int) -> int:
# Base condition: when we reach the end of the arrayif idx == len(nums):
return0# Option 1: Pick the current element if it's greater than prev pick =0if nums[idx] > prev:
pick =1+ dfs(idx +1, nums[idx])
# Option 2: Skip the current element dont_pick = dfs(idx +1, prev)
# Return the maximum of both optionsreturn max(pick, dont_pick)
# Start recursion with initial valuesreturn dfs(0, float('-inf'))
We can do better and further reduce the state stored using DP. It’s redundant to store states for allĀ iĀ havingĀ prevĀ as its previous element index. The length will always be greatest for the stateĀ (prev, prev)Ā since no more elements beforeĀ prevĀ can be taken. So we can just use a linear DP whereĀ dp[i]Ā denotes the LIS starting at indexĀ i
publicclassSolution {
publicintlengthOfLIS(int[] nums) {
int n = nums.length;
int[] memo =newint[n]; // Memoization array to track solved subproblems Arrays.fill(memo, -1); // Initialize memo arrayreturn dfs(nums, 0, -1, memo); // Start DFS with idx = 0 and prevIdx = -1 }
privateintdfs(int[] nums, int idx, int prevIdx, int[] memo) {
// Base case: when we go beyond the arrayif (idx == nums.length) {
return 0;
}
// Check the result for this index in the memo arrayif (prevIdx !=-1 && memo[prevIdx]!=-1) {
return memo[prevIdx];
}
// Option 1: Skip the current elementint dontPick = dfs(nums, idx + 1, prevIdx, memo);
// Option 2: Pick the current element (if valid)int pick = 0;
if (prevIdx ==-1 || nums[idx]> nums[prevIdx]) {
pick = 1 + dfs(nums, idx + 1, idx, memo);
}
// Update the memo array for the previous index (prevIdx) and return the resultint result = Math.max(pick, dontPick);
if (prevIdx !=-1) {
memo[prevIdx]= result;
}
return result;
}
}
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
memo = [-1] * n # Memoization array to store results for each indexdefdfs(idx: int, prev_idx: int) -> int:
# Base case: when we reach the end of the arrayif idx == n:
return0# Check if the result is already computed for this stateif prev_idx !=-1and memo[prev_idx] !=-1:
return memo[prev_idx]
# Option 1: Skip the current element dont_pick = dfs(idx +1, prev_idx)
# Option 2: Pick the current element (if valid) pick =0if prev_idx ==-1or nums[idx] > nums[prev_idx]:
pick =1+ dfs(idx +1, idx)
# Store the result in memo for the previous index (prev_idx) result = max(pick, dont_pick)
if prev_idx !=-1:
memo[prev_idx] = result
return result
# Start DFS with idx = 0 and prev_idx = -1return dfs(0, -1)
Let max[i] represent the length of the longest increasing subsequence so far.
If any element before i is smaller than nums[i], then max[i] = max(max[i], max[j]+1).
Here is an example:
classSolution {
publicintlengthOfLIS(int[] nums) {
if (nums ==null|| nums.length== 0) return 0;
int n = nums.length;
int[] dp =newint[n];
int ans = 0;
// Initialize dp array with 1s (at least each element can form a subsequence of length 1)for (int i = 0; i < n; i++) {
dp[i]= 1; // Every element starts as an LIS of 1 }
// Iterate through each elementfor (int i = 0; i < n; i++) {
// Compare with all previous elementsfor (int j = 0; j < i; j++) {
if (nums[j]< nums[i]) {
dp[i]= Math.max(dp[i], dp[j]+ 1); // Update dp[i] based on dp[j] }
}
// Update the overall maximum LIS length ans = Math.max(ans, dp[i]);
}
return ans; // Return the maximum value in dp array }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
ifnot nums: # Handle empty array casereturn0 n: int = len(nums)
dp: List[int] = [1] * n # Initialize dp array with 1s (minimum LIS length for each element) ans: int =0# Variable to store the overall LIS length# Iterate through each elementfor i in range(n):
# Compare with all previous elementsfor j in range(i): # Check all elements before index iif nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] +1) # Update dp[i] based on dp[j] ans = max(ans, dp[i]) # Update the overall maximum LIS lengthreturn ans # Return the maximum value in dp array
In the brute-force approach, we were not sure if an element should be included or not to form the longest increasing subsequence and thus we explored both options. The problem lies in knowing if an element must be included in the sequence formed till now. Let’s instead try an approach where we include element whenever possible to maximize the length and if it’s not possible, then create a new subsequence and include it.
Traverse from 0 to n-1, the DP array keep the longest sequence.
if the val is bigger than largest in the dp array, add it to the end;
if it is among the sequence, return the idx that bigger than pres, update the array with this position if val is smaller than dp[idx];
This is to keep the sequence element with the smallest number.
classSolution {
publicintlengthOfLIS(int[] nums) {
// List to represent the smallest end elements of increasing subsequences List<Integer> temp =new ArrayList<>();
for (int num : nums) {
// Use binary search to find the position of num in tempint idx = Collections.binarySearch(temp, num);
if (idx < 0) {
idx =-(idx + 1); // Convert to insertion point if not found }
// If num can replace an existing valueif (idx < temp.size()) {
temp.set(idx, num);
} else {
// If num is greater than all elements, it extends the LIS temp.add(num);
}
}
// The size of temp is the LIS lengthreturn temp.size();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
deflengthOfLIS(self, nums: List[int]) -> int:
# List to represent the smallest end elements of increasing subsequences temp: List[int] = []
for num in nums:
# Use binary search to find the index where num fits in temp idx = bisect.bisect_left(temp, num)
# If num can replace an existing valueif idx < len(temp):
temp[idx] = num
else:
# If num is greater than all elements, it extends the LIS temp.append(num)
# The size of temp is the LIS lengthreturn len(temp)
You can solve the Longest Increasing Subsequence (LIS) problem using graph theory by constructing a directed acyclic graph (DAG) where each node represents an element of the array, and there’s a directed edge from node (i) to node (j) if (nums[i] < nums[j]) and (i < j).
The task then becomes finding the longest path in this DAG, which corresponds to the LIS.
This is how the graph look for:
1
nums =[9,1,3,7,5,6,20]
graph LR;
I(9) ---> S(20)
A(1) ---> C(3)
A(1) ---> G(7)
A(1) ---> E(5)
A(1) ---> F(6)
A(1) ---> S
C ---> G & E & F & S
G ---> S
E ---> F & S
F ---> S
style A fill:#FF9933
style C fill:#FF9933
style E fill:#FF9933
style F fill:#FF9933
style S fill:#FF9933
linkStyle 1 stroke:#6f6
linkStyle 7 stroke:#6f6
linkStyle 11 stroke:#6f6
linkStyle 13 stroke:#6f6
The path marked is longest increasing subsequence or longest path in the DAG.
Here are the steps:
Graph Construction:
Represent the array elements as nodes in a graph.
For each pair of elements ((nums[i], nums[j])) where (i < j) and (nums[i] < nums[j]), add a directed edge from node (i) to node (j).
Longest Path in DAG using Dynamic Programming:
Initialize aĀ dpĀ array of the same length as the input array, with each element initially set to 1 (dp[i] = 1). The valueĀ dp[i]Ā represents the length of the longest increasing subsequence ending at indexĀ i.
For each node (i) (from (0) to (n-1)):
For each node (j) (from (0) to (i-1)):
If there’s an edge from (j) to (i) (nums[j] < nums[i]), updateĀ dp[i]: [dp[i] = \max(dp[i], dp[j] + 1)]
The length of the longest increasing subsequence is the maximum value in theĀ dpĀ array.
classSolution {
publicintlengthOfLIS(int[] nums) {
int n = nums.length;
List<Integer>[] graph =new List[n];
for (int i = 0; i < n; i++) {
graph[i]=new ArrayList<Integer>();
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i]<nums[j]) {
graph[i].add(j);
}
}
}
int dp[]=newint[n];
Arrays.fill(dp, 1);
for (int i = 0; i < n; i++) {
for (int j: graph[i]) {
dp[j]= Math.max(dp[j], dp[i]+ 1);
}
}
int ans = 1;
for (int i = 0; i < n; i++) {
ans = Math.max(ans, dp[i]);
}
return ans;
}
}