Longest Increasing Subsequence in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Increasing Subsequence (LIS) in an array?

The Longest Increasing Subsequence is the longest sequence of elements in an array such that all elements are in strictly increasing order, but not necessarily contiguous.

intermediate

What is the time complexity of the classic dynamic programming approach to find LIS?

The classic dynamic programming approach to find LIS has a time complexity of O(n²), where n is the number of elements in the array.

intermediate

In LIS problem, what does the dp[i] represent in the dynamic programming solution?

dp[i] represents the length of the Longest Increasing Subsequence that ends exactly at index i.

advanced

How can binary search improve the LIS solution's time complexity?

Using binary search on a temporary array that stores the smallest possible tail of increasing subsequences of different lengths, we can achieve O(n log n) time complexity.

beginner

What is the difference between a subsequence and a substring?

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A substring is a contiguous part of the original sequence.

What does the Longest Increasing Subsequence represent in an array?

A The sequence with the largest sum

B The longest contiguous increasing sequence

C The longest sequence of increasing elements, not necessarily contiguous

D The shortest increasing sequence

LIS is the longest sequence of increasing elements that may skip some elements, so it is not necessarily contiguous.

What is the time complexity of the naive dynamic programming solution for LIS?

A O(n²)

B O(n)

C O(n log n)

D O(log n)

The classic DP solution checks all previous elements for each element, resulting in O(n²) time.

In the DP approach, what does dp[i] store?

A Length of LIS ending at index i

B Length of LIS starting at index i

C Maximum element till index i

D Sum of elements till index i

dp[i] stores the length of the longest increasing subsequence that ends exactly at index i.

Which technique helps reduce LIS time complexity to O(n log n)?

A Sorting

B Memoization

C Brute Force

D Binary Search

Binary search is used on a temporary array to efficiently find positions to update, reducing complexity.

Which of these is true about subsequences?

A They must be contiguous

B They can skip elements but keep order

C They are always sorted

D They are always the longest sequence

Subsequences keep the original order but can skip elements.

Explain the dynamic programming approach to find the Longest Increasing Subsequence.

Think about how to build solutions for smaller subproblems and combine them.

Describe how binary search is used to optimize the LIS problem to O(n log n).

Focus on how to keep track of potential subsequences efficiently.

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