Longest Increasing Subsequence in DSA C++ - Build from Scratch

Longest Increasing Subsequence

📖 Scenario: You are analyzing a sequence of numbers representing daily stock prices. You want to find the longest period where the prices keep increasing day by day.

🎯 Goal: Build a program that finds the length of the longest increasing subsequence (LIS) in a list of integers.

📋 What You'll Learn

Create a vector called prices with the exact values: 10, 22, 9, 33, 21, 50, 41, 60

Create an integer variable called n that stores the size of prices

Create a vector called lis of size n initialized with 1s

Use nested for loops with variables i and j to compute the LIS length

Print the length of the longest increasing subsequence using std::cout

💡 Why This Matters

🌍 Real World

Finding the longest increasing subsequence helps in analyzing trends like stock prices, sales growth, or any data that changes over time.

💼 Career

Understanding LIS is important for software engineers working on algorithms, data analysis, and optimization problems.

1

Create the data vector

Create a std::vector<int> called prices with these exact values: 10, 22, 9, 33, 21, 50, 41, 60

DSA C++

#include 
#include 

int main() {
    // Create vector prices with values 10, 22, 9, 33, 21, 50, 41, 60
    // Your code here
    return 0;
}

Hint

Use std::vector<int> prices = {10, 22, 9, 33, 21, 50, 41, 60}; to create the vector.

2

Set up variables for LIS calculation

Create an integer variable called n and set it to the size of prices. Then create a std::vector<int> called lis of size n initialized with 1s.

DSA C++

#include 
#include 

int main() {
    std::vector prices = {10, 22, 9, 33, 21, 50, 41, 60};
    // Create int n as size of prices
    // Create vector lis of size n with all values 1
    // Your code here
    return 0;
}

Hint

Use int n = prices.size(); and std::vector<int> lis(n, 1);

3

Calculate the LIS length

Use nested for loops with variables i and j where i goes from 1 to n-1 and j goes from 0 to i-1. Inside, if prices[i] is greater than prices[j] and lis[i] is less than lis[j] + 1, update lis[i] to lis[j] + 1. Then create an integer variable max_lis and set it to 1. Use a for loop with variable k from 0 to n-1 to update max_lis to the maximum value in lis.

DSA C++

#include 
#include 

int main() {
    std::vector prices = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = prices.size();
    std::vector lis(n, 1);
    // Use nested for loops with i and j to update lis
    // Create int max_lis = 1
    // Use for loop with k to find max value in lis
    // Your code here
    return 0;
}

Hint

Use nested loops to update lis values and then find the maximum in lis.

4

Print the length of the longest increasing subsequence

Print the value of max_lis using std::cout followed by a newline.

DSA C++

Hint

Use std::cout << max_lis << std::endl; to print the result.

Practice

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

easy

A. The longest subsequence where numbers are equal

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

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

D. The shortest subsequence with increasing numbers

Solution

1. Step 1: Understand the problem definition

   The LIS problem looks for a subsequence where every next number is bigger than the one before it.

2. Step 2: Compare options with the definition

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

3. Final Answer:

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

4. Quick Check:

   LIS means increasing subsequence = The longest subsequence where each number is larger than the previous one [OK]

Hint: LIS means strictly increasing numbers in order [OK]

Common Mistakes:

• Confusing increasing with decreasing subsequence
• Thinking LIS means contiguous subarray
• Assuming equal numbers count as increasing

2. Which of the following is the correct way to declare a vector for storing LIS lengths in C++?

easy

A. std::vector<int> lis(n, 1);

B. vector<int> lis(n);

C. std::vector lis(n, 0);

D. vector lis<int>(n, 1);

Solution

1. Step 1: Check correct vector declaration syntax

   In C++, std::vector<int> lis(n, 1); creates a vector of size n with all values initialized to 1.

2. Step 2: Validate each option

   std::vector<int> lis(n, 1); uses correct syntax and initialization. vector<int> lis(n); misses initialization, C misses template argument, D has wrong template syntax.

3. Final Answer:

   std::vector<int> lis(n, 1); -> Option A

4. Quick Check:

   Correct vector syntax with initialization = std::vector<int> lis(n, 1); [OK]

Hint: Use std::vector<int> name(size, initial_value) [OK]

Common Mistakes:

• Omitting std:: or using wrong template syntax
• Not initializing vector values
• Using wrong brackets or missing template argument

3. What is the output of the following C++ code snippet?

std::vector<int> arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.size();
std::vector<int> lis(n, 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_lis = 0;
for (int i = 0; i < n; i++) {
  if (lis[i] > max_lis) max_lis = lis[i];
}
std::cout << max_lis << std::endl;

medium

A. 3

B. 4

C. 6

D. 5

Solution

1. Step 1: Trace LIS calculation for each element

   Calculate lis array step-by-step: lis = [1,2,1,3,2,4,4,5]

2. Step 2: Find maximum value in lis array

   Maximum lis value is 5, which is printed as output.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Max LIS length = 5 [OK]

Hint: Track lis array updates to find max length [OK]

Common Mistakes:

• Confusing subsequence with subarray
• Not updating lis[i] correctly
• Forgetting to find max after loops

4. Identify the bug in this LIS code snippet:

std::vector<int> arr = {3, 10, 2, 1, 20};
int n = arr.size();
std::vector<int> lis(n, 1);
for (int i = 0; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max_lis = *max_element(lis.begin(), lis.end());
std::cout << max_lis << std::endl;

medium

A. Missing check if lis[i] < lis[j] + 1 before updating

B. Wrong initialization of lis vector

C. Incorrect loop ranges for i and j

D. Using max_element incorrectly

Solution

1. Step 1: Analyze update condition inside nested loops

   The code updates lis[i] without checking if lis[j] + 1 is greater, causing wrong LIS values.

2. Step 2: Identify missing condition

   Adding 'if (lis[i] < lis[j] + 1)' before update fixes the bug.

3. Final Answer:

   Missing check if lis[i] < lis[j] + 1 before updating -> Option A

4. Quick Check:

   Update only if new LIS is longer [OK]

Hint: Always check if new LIS length is greater before update [OK]

Common Mistakes:

• Updating lis[i] blindly overwrites correct values
• Confusing loop indices
• Incorrect use of max_element function

5. Given the sequence {5, 7, 4, 8, 6, 9}, what is the length of the Longest Increasing Subsequence if you must also ensure the subsequence elements are at even indices only (0-based)?

medium

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Identify even indices (0-based)

   Positions 0, 2, 4 have values 5, 4, 6.

2. Step 2: Compute LIS on {5, 4, 6}

   Possible increasing subsequences: {5, 6} or {4, 6}, both length 2. No length 3 possible (5 > 4).

3. Final Answer:

   2 -> Option C

4. Quick Check:

   LIS length on even indices only = 2 [OK]

Hint: Filter even indices first, then find LIS [OK]

Common Mistakes:

• Ignoring index restriction
• Using full sequence instead of filtered
• Assuming contiguous subsequence