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

Recall & Review

beginner

What is the Longest Increasing Subsequence (LIS) in a sequence of numbers?

The Longest Increasing Subsequence is the longest sequence of numbers from the original sequence where each number is strictly greater than the previous one, but the numbers do not need to be consecutive in the original sequence.

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 length of the input sequence.

beginner

In the LIS problem, what does the dp array represent in the dynamic programming solution?

In the dynamic programming solution, dp[i] represents the length of the longest increasing subsequence that ends at index i.

advanced

What is the purpose of using binary search in the optimized LIS algorithm?

Binary search is used in the optimized LIS algorithm to efficiently find the position to replace elements in a temporary array that helps track the smallest possible tail values of increasing subsequences, reducing time complexity to O(n log n).

beginner

Can the Longest Increasing Subsequence be non-contiguous in the original sequence?

Yes, the Longest Increasing Subsequence can skip elements and does not need to be contiguous in the original sequence, only the order must be maintained.

What does the Longest Increasing Subsequence represent?

A The longest sequence of consecutive numbers

B The longest decreasing sequence

C The longest sequence of increasing numbers in order, not necessarily contiguous

D The sum of all increasing numbers

LIS is the longest sequence where each number is bigger than the previous, but numbers can be non-contiguous.

What is the time complexity of the classic dynamic programming LIS solution?

A O(n log n)

B O(n²)

C O(n)

D O(log n)

The classic DP approach uses nested loops, resulting in O(n²) time complexity.

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

A Length of LIS ending at index i

B Length of LIS starting at index i

C Maximum number in the sequence

D Index of the smallest element

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

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

A Binary Search

B Recursion

C Brute Force

D Sorting

Binary search helps efficiently update the temporary array tracking subsequence tails.

Is the LIS always a contiguous subsequence?

A Yes, always contiguous

B Only if all elements are unique

C Only if sorted

D No, can skip elements

LIS can skip elements but must keep the original order.

Explain how the dynamic programming approach finds the Longest Increasing Subsequence.

Think about how you build solutions for smaller parts to solve the whole.

Describe the optimized method to find LIS using binary search and why it is faster.

Focus on how binary search helps quickly update subsequence tails.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask you to find in a sequence of numbers?

easy

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

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

C. The longest subsequence where numbers are equal

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the LIS 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. Options B, C, and D do not describe LIS correctly.

3. Final Answer:

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

4. Quick Check:

   LIS = longest increasing subsequence [OK]

Hint: LIS means strictly increasing sequence, not equal or decreasing [OK]

Common Mistakes:

• Confusing increasing with non-decreasing
• Thinking LIS means equal numbers
• Mixing up subsequence with substring

2. Which of the following C code snippets correctly initializes the array to store LIS lengths for each element in an array arr of size n?

easy

A. int lis[n] = {0};

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

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

D. int lis[n]; memset(lis, 1, n*sizeof(int));

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because each element alone is a subsequence.

2. Step 2: Check code correctness

   int lis[n]; for(int i=0; i

3. Final Answer:

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

4. Quick Check:

   Initialize LIS array with 1 [OK]

Hint: Initialize LIS array elements to 1, not 0 [OK]

Common Mistakes:

• Using memset to set integers to 1 (wrong)
• Initializing LIS array with zeros
• Not initializing LIS array at all

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

int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
int n = 8;
int lis[8];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Calculate LIS values step-by-step

   Start with lis = {1,1,1,1,1,1,1,1} - i=1: arr[1]=22 > arr[0]=10, lis[1]=max(1,1+1)=2 - i=2: arr[2]=9 no smaller than previous, lis[2]=1 - i=3: arr[3]=33 > 22 and 10, lis[3]=max(1,2+1)=3 - i=4: arr[4]=21 > 10 but <22, lis[4]=max(1,1+1)=2 - i=5: arr[5]=50 > 33, 22, 21, lis[5]=max(1,3+1)=4 - i=6: arr[6]=41 > 33, 22, 21, lis[6]=max(1,3+1)=4 - i=7: arr[7]=60 > 50, 41, lis[7]=max(1,4+1)=5

2. Step 2: Find maximum LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   LIS length for given array = 5 [OK]

Hint: Trace LIS array updates carefully for each element [OK]

Common Mistakes:

• Counting non-increasing subsequences
• Forgetting to update lis[i] only if condition met
• Mixing up indices in nested loops

4. Identify the bug in the following C code snippet that attempts to compute the LIS length:

int arr[] = {3, 10, 2, 1, 20};
int n = 5;
int lis[5];
for(int i=0; i arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = lis[0];
for(int i=1; i max) max = lis[i];
}
printf("%d", max);

medium

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

B. The nested loops should start from i=0

C. The condition arr[i] > arr[j] should be arr[i] >= arr[j]

D. The max variable should be initialized to 0

Solution

1. Step 1: Check LIS array initialization

   LIS array elements represent length of subsequence ending at each index. Each element alone forms subsequence of length 1, so initialize lis[i] = 1.

2. Step 2: Analyze effect of initialization

   Initializing lis[i] = 0 causes all comparisons lis[i] < lis[j] + 1 to fail or produce wrong results, leading to incorrect max LIS length.

3. Final Answer:

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

4. Quick Check:

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

Hint: Always start LIS lengths at 1, not 0 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing comparison operators incorrectly
• Starting loops at wrong indices

5. Given an array arr = {5, 7, 4, 8, 6, 9}, write a C function to find the length of the Longest Increasing Subsequence using dynamic programming. What is the length of the LIS for this array?

hard

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Initialize LIS array with 1 for each element

   lis = {1,1,1,1,1,1}

2. Step 2: Update LIS values by comparing each element with previous ones

   - i=1 (7): 7 > 5, lis[1] = max(1, 1+1) = 2 - i=2 (4): 4 > 5? No, lis[2] = 1 - i=3 (8): 8 > 5, lis[3] = max(1,1+1)=2; 8 > 7, lis[3] = max(2,2+1)=3; 8 > 4, lis[3] = max(3,1+1)=3 - i=4 (6): 6 > 5, lis[4] = max(1,1+1)=2; 6 > 7? No; 6 > 4, lis[4] = max(2,1+1)=2; 6 > 8? No - i=5 (9): 9 > 5, lis[5] = max(1,1+1)=2; 9 > 7, lis[5] = max(2,2+1)=3; 9 > 4, lis[5] = max(3,1+1)=3; 9 > 8, lis[5] = max(3,3+1)=4; 9 > 6, lis[5] = max(4,2+1)=4

3. Step 3: Find maximum LIS length

   Maximum lis value is 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   LIS length for given array = 4 [OK]

Hint: Update LIS by checking all previous smaller elements [OK]

Common Mistakes:

• Not updating LIS correctly for all previous elements
• Confusing subsequence with substring
• Forgetting to initialize LIS array with 1