Longest Increasing Subsequence in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the length of the longest increasing subsequence to 1 for each element.

DSA Go

for i := range nums {
    dp[i] = [1]
}

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

A0

Bnums[i]

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp[i] to 0 causes incorrect subsequence length.

Using nums[i] instead of 1 confuses value with length.

Each element alone is a subsequence of length 1, so dp[i] should start at 1.

2fill in blank

medium

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

DSA Go

if nums[i] [1] nums[j] {
    if dp[j]+1 > dp[i] {
        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 '<' instead of '>' reverses the logic.

Using '==' does not allow increasing sequences.

We want to extend the subsequence only if nums[i] is greater than nums[j].

3fill in blank

hard

Fix the error in updating the maximum length of LIS after processing each element.

DSA Go

if dp[i] [1] maxLen {
    maxLen = dp[i]
}

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

A>

B<=

C<

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' causes maxLen to never update correctly.

Using '<=' or '>=' can cause unnecessary updates but still work.

We update maxLen only if dp[i] is greater than current maxLen.

4fill in blank

hard

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

DSA Go

for [1] := 1; [2] < len(nums); [2]++ {
    for j := 0; j < [2]; j++ {
        if nums[[1]] > nums[j] {
            if dp[j]+1 > dp[[1]] {
                dp[[1]] = dp[j] + 1
            }
        }
    }
}

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

Ai

Bj

Ck

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same variable for both loops causes errors.

Using j for outer loop conflicts with inner loop.

The outer loop variable is i, iterating from 1 to len(nums)-1.

5fill in blank

hard

Fill all three blanks to complete the LIS function returning the maximum length.

DSA Go

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

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

A1

B0

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp or maxLen to 0 causes wrong results.

Using '<' instead of '>' in maxLen update fails to track longest subsequence.

Initialize dp[i] to 1, maxLen to 1, and update maxLen if dp[i] > maxLen.

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