Longest Increasing Subsequence in Java: Explanation & Practice

Find length of longest strictly increasing subsequence

Problem summary

Given an array, find the length of the longest strictly increasing subsequence. This is a classic DP problem with O(n²) solution.

Starter code

public class Main {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        
        // dp[i] = LIS ending at index i
        // For each j < i: if nums[j] < nums[i], dp[i] = max(dp[i], dp[j]+1)
        // Print: LIS length: 4
    }
}

Expected output and test cases

[10,9,2,5,3,7,101,18] → 2,3,7,101 or 2,5,7,101
```
LIS length: 4
```
[0,1,0,3,2,3] → 0,1,2,3
```
LIS length: 4
```
[7,7,7,7] → any single 7
```
LIS length: 1
```

Hints

dp[i] represents the length of LIS ending at index i
Initialize all dp[i] = 1 (each element is a subsequence of length 1)
For each i, check all j < i: if nums[j] < nums[i], we can extend
Answer is max of all dp[i]

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler