Longest Increasing Subsequence in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of LIS length calculation

What is the output of the following Java code that calculates the length of the Longest Increasing Subsequence (LIS) for the given array?

DSA Java

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

    public static void main(String[] args) {
        int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(arr));
    }
}

A 4

B 3

C 5

D 6

💡 Hint

Trace the dp array updates for each element comparing with previous elements.

The longest increasing subsequence is [2, 3, 7, 101], which has length 4.

🧠 Conceptual

intermediate

Understanding LIS subsequence reconstruction

Given the dp array from LIS length calculation, which additional data structure helps reconstruct the actual longest increasing subsequence?

A A queue to hold elements as they are processed

B A stack to store all elements in sorted order

C An array to store the previous index of the element in the LIS

D A hash set to track visited elements

💡 Hint

Think about how to trace back the LIS elements after computing lengths.

To reconstruct the LIS, we keep track of the previous index for each element that forms the LIS, allowing us to backtrack from the maximum dp index.

❓ Predict Output

advanced

Output of LIS length using binary search optimization

What is the output of the following Java code that uses a binary search approach to find the length of the Longest Increasing Subsequence?

DSA Java

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

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9};
        System.out.println(lengthOfLIS(arr));
    }
}

A 4

B 5

C 6

D 7

💡 Hint

The binary search method builds a list representing the smallest possible tail for increasing subsequences of different lengths.

The longest increasing subsequence length is 5 for the input array, for example [0, 2, 6, 9, 14].

🔧 Debug

advanced

Identify the error in LIS length calculation code

What error will the following Java code produce when run, and why?

DSA Java

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

    public static void main(String[] args) {
        int[] arr = {3, 10, 2, 1, 20};
        System.out.println(lengthOfLIS(arr));
    }
}

A The output is 2 because dp[0] is never initialized to 1

B The output is 3, which is correct

C The code throws ArrayIndexOutOfBoundsException

D The output is 1 because the loop skips updating dp correctly

💡 Hint

Check initialization of dp array elements before loops.

dp[0] remains 0 because the loop starts from i=1 and dp[0] is never set to 1, so max remains 0 or less than expected.

🚀 Application

expert

Longest Increasing Subsequence in a real-world scenario

You have a list of daily stock prices. You want to find the longest period where the stock price strictly increases day by day. Which algorithmic approach best fits this problem and why?

A Use the dynamic programming LIS algorithm to find the longest increasing subsequence of prices

B Use a hash map to store prices and find duplicates

C Use a sorting algorithm to sort prices and count consecutive days

D Use a sliding window to find the longest subarray with increasing prices

💡 Hint

Think about continuous days versus subsequence with gaps.

The problem asks for the longest continuous increasing period (subarray), not subsequence. Sliding window or two-pointer approach is best for subarrays.

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