Java Program to Find Longest Increasing Subsequence

You can find the longest increasing subsequence in Java by using dynamic programming with an array to track lengths and updating it with for loops; for example, use int[] dp = new int[n] and update it to find the maximum length subsequence.

Examples

Input[10, 22, 9, 33, 21, 50, 41, 60]

Output5

Input[3, 10, 2, 1, 20]

Output3

Input[3, 2]

Output1

How to Think About It

To find the longest increasing subsequence, think of checking each number and seeing how long an increasing sequence ending at that number can be by looking at all previous numbers smaller than it. Keep track of the longest length found so far and update it as you go through the list.

Algorithm

1

Initialize an array dp of the same length as input with all values 1.

2

For each element from the second to the last, check all previous elements.

3

If a previous element is smaller, update dp[current] to max(dp[current], dp[previous] + 1).

4

Keep track of the maximum value in dp during the process.

5

Return the maximum value found in dp as the length of the longest increasing subsequence.

Code

java

public class LIS {
    public static int longestIncreasingSubsequence(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > maxLen) maxLen = dp[i];
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
        System.out.println(longestIncreasingSubsequence(arr));
    }
}

Output

5

Dry Run

Let's trace the example [10, 22, 9, 33, 21, 50, 41, 60] through the code

1

Initialize dp array

dp = [1, 1, 1, 1, 1, 1, 1, 1]

2

Check element 22 at index 1

Compare with 10: 10 < 22, dp[1] = max(1, dp[0]+1) = 2; dp = [1, 2, 1, 1, 1, 1, 1, 1]

3

Check element 9 at index 2

Compare with 10 and 22: no smaller before 9, dp stays 1

4

Check element 33 at index 3

Compare with 10,22,9: max dp before smaller is dp[1]=2, dp[3]=3; dp = [1,2,1,3,1,1,1,1]

5

Check element 21 at index 4

Compare with 10,22,9,33: max dp before smaller is dp[1]=2, dp[4]=3; dp = [1,2,1,3,3,1,1,1]

6

Check element 50 at index 5

Compare with all before smaller: max dp is dp[3]=3, dp[5]=4; dp = [1,2,1,3,3,4,1,1]

7

Check element 41 at index 6

Compare with all before smaller: max dp is dp[4]=3, dp[6]=4; dp = [1,2,1,3,3,4,4,1]

8

Check element 60 at index 7

Compare with all before smaller: max dp is dp[5]=4, dp[7]=5; dp = [1,2,1,3,3,4,4,5]

Index	Element	dp Array	Max Length
0	10	[1,1,1,1,1,1,1,1]	1
1	22	[1,2,1,1,1,1,1,1]	2
2	9	[1,2,1,1,1,1,1,1]	2
3	33	[1,2,1,3,1,1,1,1]	3
4	21	[1,2,1,3,3,1,1,1]	3
5	50	[1,2,1,3,3,4,1,1]	4
6	41	[1,2,1,3,3,4,4,1]	4
7	60	[1,2,1,3,3,4,4,5]	5

Why This Works

Step 1: Initialize dp array

Each position starts with 1 because the smallest increasing subsequence including that element is the element itself.

Step 2: Update dp values

For each element, check all previous elements; if a previous element is smaller, update the current dp value to the longest subsequence ending there plus one.

Step 3: Find maximum length

Keep track of the maximum dp value found, which represents the length of the longest increasing subsequence.

Alternative Approaches

Binary Search Optimization

java

import java.util.*;
public class LIS {
    public static int lengthOfLIS(int[] nums) {
        ArrayList<Integer> sub = new ArrayList<>();
        for (int num : nums) {
            int i = Collections.binarySearch(sub, num);
            if (i < 0) i = -(i + 1);
            if (i == sub.size()) sub.add(num);
            else sub.set(i, num);
        }
        return sub.size();
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
        System.out.println(lengthOfLIS(arr));
    }
}

This approach uses binary search to maintain a list of smallest possible tails for subsequences, reducing time complexity to O(n log n) but is more complex to understand.

Complexity: O(n^2) time, O(n) space

Time Complexity

The nested loops cause the time to grow roughly with the square of the input size, as each element compares with all before it.

Space Complexity

An extra array dp of size n is used to store lengths, so space grows linearly with input size.

Which Approach is Fastest?

The binary search method reduces time to O(n log n) but is harder to implement and understand compared to the simpler O(n^2) dynamic programming.

Approach	Time	Space	Best For
Dynamic Programming	O(n^2)	O(n)	Simplicity and clarity
Binary Search Optimization	O(n log n)	O(n)	Large inputs needing speed