Longest Increasing Subsequence in DSA Go - Deep Dive

Overview - Longest Increasing Subsequence

What is it?

The Longest Increasing Subsequence (LIS) is a sequence of numbers taken from a list where each number is bigger than the one before it, and the sequence is as long as possible. It does not have to be made of consecutive numbers from the original list, but the order must stay the same. For example, in the list [3, 10, 2, 1, 20], the LIS is [3, 10, 20]. This concept helps us find patterns and trends in data.

Why it matters

Without the ability to find the longest increasing subsequence, it would be hard to analyze trends or progressions in data, such as stock prices or skill improvements. It helps in optimizing problems where order matters but not necessarily continuity. Many real-world problems like scheduling, genetics, and data compression rely on this concept to find the best possible increasing pattern.

Where it fits

Before learning LIS, you should understand arrays or lists and basic loops. After LIS, you can explore dynamic programming deeply, advanced sequence problems, and optimization techniques like binary search in DP.

Mental Model

Core Idea

The Longest Increasing Subsequence is the longest ordered list you can make by picking numbers from the original list without changing their order, where each number is bigger than the one before.

Think of it like...

Imagine you are climbing a staircase but you can only step on stairs that are higher than the last one you stepped on. You want to climb as many stairs as possible without stepping down or staying on the same level.

Original list: 3  10  2  1  20
Possible subsequences:
 3 -> 10 -> 20 (length 3)
 2 -> 20 (length 2)
 1 -> 20 (length 2)
Longest Increasing Subsequence: 3 -> 10 -> 20

Build-Up - 7 Steps

1

Foundation

Understanding Subsequences

Concept: Learn what a subsequence is and how it differs from a substring or subarray.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, from [3, 10, 2, 1, 20], subsequences include [3, 2, 20], [10, 1], or [3, 10, 20]. Unlike substrings, subsequences do not need to be contiguous.

Result

You can identify many subsequences from a list by skipping elements but keeping order.

Understanding subsequences is key because LIS is about finding the longest increasing one among all possible subsequences.

2

Foundation

Defining Increasing Subsequences

Concept: Introduce the idea that the subsequence must be strictly increasing.

An increasing subsequence means each number is bigger than the one before it. For example, [3, 10, 20] is increasing, but [3, 2, 20] is not because 2 is less than 3. This rule filters subsequences to only those that grow in value.

Result

You can now distinguish which subsequences qualify as increasing.

Knowing the strict increase rule narrows down the subsequences to those that show growth or progress.

3

Intermediate

Brute Force Approach to LIS

🤔Before reading on: do you think checking all subsequences is efficient or inefficient? Commit to your answer.

Concept: Explore the naive method of checking every subsequence to find the longest increasing one.

The brute force way tries all subsequences, checks if they are increasing, and keeps track of the longest. This involves generating 2^n subsequences for a list of length n, which is very slow for large lists.

Result

Brute force works but is too slow for big inputs.

Understanding brute force shows why we need smarter methods to handle bigger problems efficiently.

4

Intermediate

Dynamic Programming Solution

🤔Before reading on: do you think storing previous results can speed up LIS calculation? Commit to your answer.

Concept: Use dynamic programming to build solutions for smaller parts and combine them to solve the whole problem.

Create an array dp where dp[i] stores the length of the LIS ending at index i. For each element, look back at all previous elements smaller than it and update dp[i] = max(dp[i], dp[j] + 1). The answer is the max value in dp after processing all elements.

Result

This method runs in O(n^2) time and finds the LIS length efficiently.

Dynamic programming avoids repeated work by remembering solutions to smaller subproblems.

5

Intermediate

Reconstructing the LIS Sequence

🤔Before reading on: do you think knowing the length alone is enough to get the actual LIS? Commit to your answer.

Concept: Learn how to track the actual numbers in the LIS, not just its length.

Along with dp, keep a parent array to remember which index led to the current dp[i]. After filling dp, find the index with the max dp value and follow parents backward to reconstruct the LIS sequence.

Result

You get the exact longest increasing subsequence, not just its length.

Tracking parents lets you recover the solution path, which is often needed in real problems.

6

Advanced

Optimized O(n log n) Approach

🤔Before reading on: do you think binary search can help speed up LIS? Commit to your answer.

Concept: Use a clever method with binary search to improve performance from O(n^2) to O(n log n).

Maintain an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, use binary search to find where it fits in tails and update tails accordingly. The length of tails is the LIS length.

Result

This method finds the LIS length much faster, suitable for large inputs.

Combining binary search with dynamic programming ideas leads to a powerful optimization.

7

Expert

Handling Equal Elements and Variations

🤔Before reading on: do you think LIS always requires strictly increasing sequences? Commit to your answer.

Concept: Explore variations like non-decreasing subsequences and how to adapt algorithms.

Sometimes problems ask for longest non-decreasing subsequence where equal elements are allowed. Adjust comparisons in DP and binary search accordingly. Also, learn how to modify reconstruction to handle these cases.

Result

You can solve a wider range of sequence problems by tweaking LIS rules.

Knowing how to adapt LIS algorithms to variations is crucial for real-world and contest problems.

Under the Hood

The DP approach builds a table where each entry depends on previous entries, avoiding repeated calculations. The optimized method uses a tails array to keep track of potential subsequence ends, and binary search quickly finds where to place new elements. This reduces the problem to maintaining sorted order of tails and updating them efficiently.

Why designed this way?

The DP method was designed to break down a complex problem into smaller overlapping subproblems. The O(n log n) method was created to overcome the inefficiency of checking all pairs by cleverly using binary search, a well-known fast search technique, to maintain subsequence candidates.

Input: [3, 10, 2, 1, 20]

DP array (lengths):
Index: 0  1   2  3  4
Value:3 10   2  1 20
DP:   1  2   1  1  3

Tails array during O(n log n):
Step 1: tails = [3]
Step 2: tails = [3, 10]
Step 3: tails = [2, 10]
Step 4: tails = [1, 10]
Step 5: tails = [1, 10, 20]

Length of tails = 3 (LIS length)

Myth Busters - 4 Common Misconceptions

Quick: Does the LIS have to be made of consecutive elements? Commit yes or no.

Common Belief: The longest increasing subsequence must be made of consecutive elements in the list.

Reality: The LIS can skip elements as long as the order is maintained; it does not need to be consecutive.

Why it matters: Believing LIS requires consecutive elements limits the solution space and leads to incorrect answers.

Quick: Is the LIS always unique? Commit yes or no.

Common Belief: There is only one longest increasing subsequence for any list.

Reality: There can be multiple different LIS with the same maximum length.

Why it matters: Assuming uniqueness can cause errors when reconstructing the sequence or counting LIS.

Quick: Does the O(n log n) method give the actual LIS sequence? Commit yes or no.

Common Belief: The optimized O(n log n) method directly returns the LIS sequence.

Reality: It only returns the length of the LIS; reconstructing the sequence requires extra work.

Why it matters: Misunderstanding this leads to incomplete solutions when the actual sequence is needed.

Quick: Can LIS include equal elements if the problem states strictly increasing? Commit yes or no.

Common Belief: Equal elements can be part of the LIS even if it says strictly increasing.

Reality: Strictly increasing means each next element must be greater, not equal.

Why it matters: Ignoring this causes wrong LIS calculations and incorrect results.

Expert Zone

1

The tails array in the O(n log n) method does not represent a real subsequence but helps track potential ends of subsequences.

2

Reconstructing the LIS from the O(n log n) method requires maintaining additional arrays to track predecessors, which is often overlooked.

3

The LIS problem can be extended to multidimensional sequences, but the complexity increases significantly.

When NOT to use

LIS algorithms are not suitable when the order of elements can be changed or when subsequences must be contiguous. For contiguous increasing sequences, use Longest Increasing Substring or similar. For unordered sets, sorting or other methods are better.

Production Patterns

LIS is used in version control systems to find differences between files, in bioinformatics to analyze DNA sequences, and in finance to detect trends. Professionals often combine LIS with other algorithms like segment trees or Fenwick trees for range queries.

Connections

Dynamic Programming

LIS is a classic example that builds on dynamic programming principles.

Mastering LIS helps understand how to break problems into overlapping subproblems and build solutions bottom-up.

Binary Search

The optimized LIS method uses binary search to speed up updates.

Knowing binary search enables transforming quadratic DP solutions into faster ones by efficient searching.

Genetics Sequence Alignment

Both LIS and sequence alignment find ordered patterns within sequences.

Understanding LIS deepens insight into how biological sequences are compared and matched for similarities.

Common Pitfalls

#1 Trying to find LIS by sorting the list first.

Wrong approach:

Given list = [3, 10, 2, 1, 20]
Sorted list = [1, 2, 3, 10, 20]
Return sorted list as LIS.

Correct approach:

Use DP or optimized method on original list without sorting to find LIS.

Root cause:

Misunderstanding that LIS must maintain original order, which sorting breaks.

#2 Using <= instead of < in comparisons for strictly increasing subsequence.

Wrong approach:

if nums[j] <= nums[i] then update dp[i] = max(dp[i], dp[j] + 1)

Correct approach:

if nums[j] < nums[i] then update dp[i] = max(dp[i], dp[j] + 1)

Root cause:

Confusing strictly increasing with non-decreasing sequences.

#3 Assuming the O(n log n) tails array is the LIS sequence.

Wrong approach:

Return tails array as the LIS sequence directly.

Correct approach:

Use tails length as LIS length; reconstruct sequence with extra tracking arrays.

Root cause:

Misinterpreting the purpose of tails array as actual subsequence.

Key Takeaways

The Longest Increasing Subsequence is about finding the longest ordered sequence where each number is bigger than the previous, without needing to be consecutive.

Dynamic programming solves LIS by building solutions for smaller parts and combining them, reducing repeated work.

The optimized O(n log n) method uses binary search on a helper array to speed up the process but requires extra steps to reconstruct the sequence.

LIS problems have variations like non-decreasing subsequences, and understanding these differences is crucial for correct solutions.

Misconceptions about continuity, uniqueness, and reconstruction can lead to wrong answers, so careful understanding is essential.

Practice

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

easy

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

B. The longest contiguous subarray with equal elements

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

D. The sum of all increasing numbers in the sequence

Solution

1. Step 1: Understand the LIS definition

   The LIS is a subsequence (not necessarily contiguous) where every next number is strictly greater than the previous.

2. Step 2: Compare options with definition

   The longest subsequence where each number is larger than the previous one matches the LIS definition exactly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

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

Common Mistakes:

• Confusing subsequence with subarray
• Thinking LIS requires contiguous elements
• Mixing increasing with decreasing sequences

2. Which of the following Go code snippets correctly initializes a slice to store LIS lengths for each element in an input array nums?

easy

A. lis := make([]int, 0, len(nums))

B. lis := []int{}

C. var lis [len(nums)]int

D. lis := make([]int, len(nums))

Solution

1. Step 1: Understand slice initialization for fixed length

   We need a slice with length equal to input length to store LIS lengths at each index.

2. Step 2: Check each option

   lis := make([]int, len(nums)) creates a slice with length len(nums), ready to store values. lis := []int{} creates empty slice with length 0. var lis [len(nums)]int is invalid syntax for arrays with dynamic length. lis := make([]int, 0, len(nums)) creates slice with length 0 but capacity len(nums), so cannot index directly.

3. Final Answer:

   lis := make([]int, len(nums)) -> Option D

4. Quick Check:

   Slice with length = len(nums) for LIS storage [OK]

Hint: Use make with length for direct indexing [OK]

Common Mistakes:

• Using empty slice without length
• Trying to declare array with variable length
• Confusing capacity with length

3. What is the output of the following Go code that calculates the length of the LIS for nums := []int{10, 9, 2, 5, 3, 7, 101, 18}?

func lengthOfLIS(nums []int) int {
    lis := make([]int, len(nums))
    for i := range lis {
        lis[i] = 1
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && lis[i] < lis[j]+1 {
                lis[i] = lis[j] + 1
            }
        }
    }
    maxLen := 0
    for _, length := range lis {
        if length > maxLen {
            maxLen = length
        }
    }
    return maxLen
}

fmt.Println(lengthOfLIS(nums))

medium

A. 4

B. 3

C. 5

D. 6

Solution

1. Step 1: Initialize LIS array with 1s

   Each element starts with LIS length 1 (itself).

2. Step 2: Update LIS values by checking previous elements

   Check pairs (i,j) where nums[i] > nums[j], update lis[i] = max(lis[i], lis[j]+1).

3. Step 3: Calculate max LIS length

   For given nums, LIS is [2,3,7,101] length 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   LIS length for example = 4 [OK]

Hint: Trace LIS updates for each element [OK]

Common Mistakes:

• Confusing subsequence with subarray
• Not updating lis[i] correctly
• Forgetting to initialize lis with 1

4. Identify the bug in this Go function that attempts to compute the LIS length:

func lengthOfLIS(nums []int) int {
    lis := make([]int, len(nums))
    for i := 0; i < len(nums); i++ {
        lis[i] = 0
    }
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && lis[i] < lis[j] + 1 {
                lis[i] = lis[j] + 1
            }
        }
    }
    maxLen := 0
    for _, length := range lis {
        if length > maxLen {
            maxLen = length
        }
    }
    return maxLen
}

medium

A. lis slice is initialized with zeros instead of ones

B. The outer loop should start from 0 instead of 1

C. The condition nums[i] > nums[j] is incorrect

D. maxLen should be initialized to 1 instead of 0

Solution

1. Step 1: Check lis initialization

   lis should start with 1 for each element because each element alone is a subsequence of length 1.

2. Step 2: Effect of zero initialization

   Starting with 0 causes maxLen to be zero if no updates happen, giving wrong result.

3. Final Answer:

   lis slice is initialized with zeros instead of ones -> Option A

4. Quick Check:

   Initialize lis with 1, not 0 [OK]

Hint: Initialize LIS array elements to 1 [OK]

Common Mistakes:

• Starting lis values at 0
• Wrong loop start index
• Misunderstanding LIS condition

5. Given the sequence nums := []int{3, 10, 2, 1, 20}, which of the following is the correct longest increasing subsequence returned by a function that reconstructs the LIS (not just its length)?

hard

A. [2, 10, 20]

B. [3, 10, 20]

C. [1, 2, 20]

D. [3, 2, 20]

Solution

1. Step 1: Identify increasing subsequences

   Check subsequences where each next number is bigger than previous.

2. Step 2: Find longest valid subsequence

   Possible LIS are [3,10,20] and [1,20], but [3,10,20] is longer with length 3.

3. Step 3: Verify options

   [3, 10, 20] matches the longest increasing subsequence. [2, 10, 20] and C start with smaller numbers but 2 is after 10 in original, so invalid subsequence. [3, 2, 20] is not increasing.

4. Final Answer:

   [3, 10, 20] -> Option B

5. Quick Check:

   Longest increasing subsequence = [3, 10, 20] [OK]

Hint: Check order and increasing property carefully [OK]

Common Mistakes:

• Choosing subsequences not in original order
• Picking non-increasing sequences
• Confusing length with actual subsequence