Longest Increasing Subsequence in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the dp array with 1s for each element.

DSA Java

int[] dp = new int[n];
for (int i = 0; i < n; i++) {
    dp[i] = [1];
}

Drag options to blanks, or click blank then click option'

A1

Bn

Ci

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp elements to 0 instead of 1.

Using the index i as the initial value.

Each element starts as a subsequence of length 1 by itself.

2fill in blank

medium

Complete the code to check if the current element can extend the subsequence ending at j.

DSA Java

if (arr[i] [1] arr[j]) {
    dp[i] = Math.max(dp[i], dp[j] + 1);
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= or <= instead of strictly > or <.

Using equality check instead of comparison.

We want to extend the subsequence only if current element is greater than previous.

3fill in blank

hard

Fix the error in the code to update the maximum length of LIS found so far.

DSA Java

int maxLen = 1;
for (int i = 0; i < n; i++) {
    maxLen = Math.[1](maxLen, dp[i]);
}

Drag options to blanks, or click blank then click option'

Amin

Bsum

Cabs

Dmax

Attempts:

3 left

💡 Hint

Common Mistakes

Using Math.min which gives the smallest value.

Using Math.abs or Math.sum which are incorrect here.

We want the maximum length, so use Math.max to update maxLen.

4fill in blank

hard

Fill both blanks to complete the nested loops for LIS calculation.

DSA Java

for (int i = [1]; i < n; i++) {
    for (int j = [2]; j < i; j++) {
        if (arr[i] > arr[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
}

Drag options to blanks, or click blank then click option'

A1

B0

Ci

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Starting outer loop from 0 causing redundant checks.

Starting inner loop from 1 missing the first element.

The outer loop starts from 1 because the first element is base case. Inner loop runs from 0 to i-1.

5fill in blank

hard

Fill all three blanks to create a map of element to its LIS length if length is greater than 1.

DSA Java

Map<Integer, Integer> lisMap = new HashMap<>();
for (int i = 0; i < n; i++) {
    if (dp[i] [1] 1) {
        lisMap.put(arr[[2]], dp[[3]]);
    }
}

Drag options to blanks, or click blank then click option'

A>

Bi

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using equality check instead of greater than.

Using different indices for key and value.

We add elements with LIS length greater than 1 to the map using their index i.

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