Longest Increasing Subsequence in DSA Java

Mental Model

Find the longest sequence of numbers that keep going up without needing to be next to each other. We want the biggest chain where each number is bigger than the one before.

Analogy: Imagine climbing stairs where you can skip steps but must always go up. The longest path you can climb without going down is like the longest increasing subsequence.

Array: [10] -> [22] -> [9] -> [33] -> [21] -> [50] -> [41] -> [60]
LIS: 10 -> 22 -> 33 -> 50 -> 60

Dry Run Walkthrough

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

Goal: Find the length of the longest increasing subsequence in the array

Step 1: Start with first element, LIS length at index 0 is 1

LIS lengths: [1, _, _, _, _, _, _, _]

Why: Each element alone is a subsequence of length 1

Step 2: Check element 22 at index 1: 22 > 10, so LIS at 1 is LIS at 0 + 1 = 2

LIS lengths: [1, 2, _, _, _, _, _, _]

Why: 22 can extend the subsequence ending at 10

Step 3: Check element 9 at index 2: 9 is not greater than 10 or 22, so LIS at 2 is 1

LIS lengths: [1, 2, 1, _, _, _, _, _]

Why: 9 starts a new subsequence since it can't extend previous ones

Step 4: Check element 33 at index 3: 33 > 10 (LIS 1), 33 > 22 (LIS 2), 33 > 9 (LIS 1), max LIS before is 2, so LIS at 3 is 3

LIS lengths: [1, 2, 1, 3, _, _, _, _]

Why: 33 extends the longest subsequence ending before it

Step 5: Check element 21 at index 4: 21 > 10 (LIS 1), 21 < 22, 21 > 9 (LIS 1), max LIS before is 1, so LIS at 4 is 2

LIS lengths: [1, 2, 1, 3, 2, _, _, _]

Why: 21 extends subsequence ending at 10 or 9 but not 22

Step 6: Check element 50 at index 5: 50 > 10 (1), 50 > 22 (2), 50 > 9 (1), 50 > 33 (3), 50 > 21 (2), max LIS before is 3, so LIS at 5 is 4

LIS lengths: [1, 2, 1, 3, 2, 4, _, _]

Why: 50 extends the longest subsequence ending before it

Step 7: Check element 41 at index 6: 41 > 10 (1), 41 > 22 (2), 41 > 9 (1), 41 > 33 (3), 41 > 21 (2), 41 < 50, max LIS before is 3, so LIS at 6 is 4

LIS lengths: [1, 2, 1, 3, 2, 4, 4, _]

Why: 41 extends the longest subsequence ending before it but less than 50

Step 8: Check element 60 at index 7: 60 > all previous, max LIS before is 4, so LIS at 7 is 5

LIS lengths: [1, 2, 1, 3, 2, 4, 4, 5]

Why: 60 extends the longest subsequence ending before it

Result:

LIS lengths: [1, 2, 1, 3, 2, 4, 4, 5]
Longest Increasing Subsequence length = 5

Annotated Code

DSA Java

public class LongestIncreasingSubsequence {

    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] lis = new int[n];
        for (int i = 0; i < n; i++) {
            lis[i] = 1; // each element alone is length 1
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1); // extend subsequence
                }
            }
        }
        int max = 1;
        for (int length : lis) {
            if (length > max) max = length; // find max LIS length
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {10, 22, 9, 33, 21, 50, 41, 60};
        int result = lengthOfLIS(nums);
        System.out.println("Longest Increasing Subsequence length = " + result);
    }
}

lis[i] = 1; // each element alone is length 1

initialize LIS length for each element as 1

if (nums[i] > nums[j]) {

check if current element can extend subsequence ending at j

lis[i] = Math.max(lis[i], lis[j] + 1); // extend subsequence

update LIS length at i if extending subsequence at j is longer

if (length > max) max = length; // find max LIS length

track maximum LIS length found so far

Output

Longest Increasing Subsequence length = 5

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to find increasing subsequences

Space: O(n) because we store LIS lengths for each element in an array

vs Alternative: This dynamic programming approach is faster than checking all subsequences (which is exponential), but slower than the optimized O(n log n) method using binary search.

Edge Cases

empty array

returns 0 because there are no elements to form a subsequence

DSA Java

if (nums == null || nums.length == 0) return 0;

array with one element

returns 1 because the single element itself is the longest subsequence

DSA Java

lis[i] = 1; // each element alone is length 1

all elements equal

returns 1 because no element is greater than previous, so longest subsequence is any single element

DSA Java

if (nums[i] > nums[j]) {

When to Use This Pattern

When you see a problem asking for the longest sequence of increasing numbers inside an array, use the Longest Increasing Subsequence pattern because it efficiently finds the longest chain without requiring elements to be next to each other.

Common Mistakes

Mistake: Updating LIS length without checking if current element is greater than previous elements
Fix: Add condition to update LIS only if nums[i] > nums[j]

Mistake: Not initializing LIS array elements to 1
Fix: Initialize each LIS length to 1 because each element alone is a subsequence

Summary

Finds the length of the longest increasing subsequence in an array.

Use when you need the longest chain of increasing numbers that are not necessarily next to each other.

Remember each element alone starts a subsequence of length 1, and you build longer subsequences by extending smaller ones.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given sequence of numbers?

easy

A. The longest subsequence with all equal numbers

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence with alternating increasing and decreasing numbers

D. The longest subsequence where each number is larger than the previous one

Solution

1. Step 1: Understand the problem definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly, while others describe different patterns.

3. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option D

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

Hint: Look for strictly increasing order in subsequence [OK]

Common Mistakes:

• Confusing subsequence with substring
• Thinking LIS means non-decreasing instead of strictly increasing
• Mixing up increasing with decreasing sequences

2. Which of the following Java code snippets correctly initializes an array to store the length of LIS ending at each index for an input array arr of size n?

easy

A. int[] lis = new int[n]; lis.fill(1);

B. int[] lis = new int[n]; for(int i=0; i

C. int[] lis = new int[n]; for(int i=0; i

D. int lis[] = new int[n]; Arrays.fill(lis, 0);

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because the smallest subsequence is the element itself.

2. Step 2: Check code correctness

   int[] lis = new int[n]; for(int i=0; ifill on array. int lis[] = new int[n]; Arrays.fill(lis, 0); fills with 0, incorrect for LIS.

3. Final Answer:

   int[] lis = new int[n]; for(int i=0; i -> Option C

4. Quick Check:

   Initialize LIS array with 1s [OK]

Hint: Initialize LIS array with 1 for each element [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Using non-existent array methods like fill()
• Not initializing LIS array before DP

3. What is the output of the following Java code snippet that calculates the length of the Longest Increasing Subsequence for the array arr = {10, 22, 9, 33, 21, 50, 41, 60}?

int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.length;
int[] lis = new int[n];
for (int i = 0; i < n; i++) lis[i] = 1;
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < n; i++) {
  if (lis[i] > max) max = lis[i];
}
System.out.println(max);

medium

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Calculate LIS array values

   For each element, find LIS ending there: - arr[0]=10: lis=1 - arr[1]=22 >10: lis=2 - arr[2]=9: lis=1 - arr[3]=33 >22: lis=3 - arr[4]=21 >10 but <22: lis=2 - arr[5]=50 >33: lis=4 - arr[6]=41 >33 but <50: lis=4 - arr[7]=60 >50: lis=5

2. Step 2: Find max LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Max LIS length = 5 [OK]

Hint: Trace LIS array updates step-by-step [OK]

Common Mistakes:

• Confusing subsequence length with subarray length
• Not updating lis[i] correctly inside nested loops
• Forgetting to find max LIS after filling array

4. Identify the bug in the following Java code snippet that attempts to compute the length of the Longest Increasing Subsequence for array arr:

int[] lis = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
  lis[i] = 0;
}
for (int i = 1; i < arr.length; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < lis.length; i++) {
  if (lis[i] > max) max = lis[i];
}
System.out.println(max);

medium

A. LIS array should be initialized with 1, not 0

B. The inner loop should start from i+1 instead of 0

C. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

D. The max variable should be initialized to Integer.MIN_VALUE

Solution

1. Step 1: Check LIS array initialization

   LIS array must start with 1 for each element because each element alone forms a subsequence of length 1. Initializing with 0 causes incorrect LIS lengths.

2. Step 2: Verify loops and conditions

   Inner loop and comparison are correct. Max initialization to 0 is fine since LIS lengths are positive.

3. Final Answer:

   LIS array should be initialized with 1, not 0 -> Option A

4. Quick Check:

   Initialize LIS with 1 to avoid zero-length subsequences [OK]

Hint: Always start LIS array values at 1 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing loop ranges incorrectly
• Misunderstanding LIS condition comparison

5. Given the array arr = {3, 10, 2, 1, 20}, which of the following sequences is the Longest Increasing Subsequence (LIS)?

hard

A. [1, 2, 3]

B. [3, 10, 20]

C. [10, 20]

D. [3, 2, 1, 20]

Solution

1. Step 1: Identify increasing subsequences

   Check each option for strictly increasing order: - [3, 10, 20]: 3 < 10 < 20 (valid) - [3, 2, 1, 20]: 3 > 2 > 1 (not increasing) - [10, 20]: 10 < 20 (valid but shorter) - [1, 2, 3]: 1 < 2 < 3 (valid but not a subsequence in original order)

2. Step 2: Compare lengths of valid subsequences

   [3, 10, 20] length is 3, [10, 20] length is 2, [1, 2, 3] length is 3 but elements not in original order (subsequence must follow original order). [1, 2, 3] is invalid as subsequence because 1 comes after 3 in original array.

3. Final Answer:

   [3, 10, 20] -> Option B

4. Quick Check:

   LIS must be increasing and follow original order [OK]

Hint: Check subsequence order matches original array [OK]

Common Mistakes:

• Choosing subsequence not in original order
• Confusing increasing with non-decreasing
• Ignoring subsequence length