Longest Increasing Subsequence in DSA Go

Mental Model

Find the longest sequence of numbers that keeps going up without rearranging the original list.

Analogy: Imagine climbing stairs where each step is higher than the last one you stepped on, but you can skip some steps to keep going up as long as possible.

Array: [3] -> [1] -> [5] -> [2] -> [6] -> [4] -> [9]
LIS:  ↑     ↑     ↑     ↑     ↑     ↑     ↑

Dry Run Walkthrough

Input: list: [3, 1, 5, 2, 6, 4, 9]

Goal: Find the longest increasing subsequence in the list

Step 1: Start with first element 3, LIS length is 1 at index 0

LIS lengths: [1, _, _, _, _, _, _]

Why: Each element alone is at least a subsequence of length 1

Step 2: Check element 1: smaller than 3, so LIS length is 1 at index 1

LIS lengths: [1, 1, _, _, _, _, _]

Why: 1 cannot extend 3, so start new subsequence

Step 3: Check element 5: greater than 3 and 1, update LIS length to 2 at index 2

LIS lengths: [1, 1, 2, _, _, _, _]

Why: 5 can extend subsequence ending at 3 or 1

Step 4: Check element 2: greater than 1 but less than 3 and 5, LIS length is 2 at index 3

LIS lengths: [1, 1, 2, 2, _, _, _]

Why: 2 extends subsequence ending at 1

Step 5: Check element 6: greater than 5 and 2, update LIS length to 3 at index 4

LIS lengths: [1, 1, 2, 2, 3, _, _]

Why: 6 extends subsequence ending at 5 or 2

Step 6: Check element 4: greater than 2 but less than 5 and 6, LIS length is 3 at index 5

LIS lengths: [1, 1, 2, 2, 3, 3, _]

Why: 4 extends subsequence ending at 2

Step 7: Check element 9: greater than 6 and 4, update LIS length to 4 at index 6

LIS lengths: [1, 1, 2, 2, 3, 3, 4]

Why: 9 extends subsequence ending at 6 or 4

Result:

Longest Increasing Subsequence length is 4
One LIS is: 1 -> 2 -> 4 -> 9

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func longestIncreasingSubsequence(nums []int) (int, []int) {
	if len(nums) == 0 {
		return 0, []int{}
	}
	lengths := make([]int, len(nums))
	prev := make([]int, len(nums))
	for i := range prev {
		prev[i] = -1
	}
	maxLen := 1
	maxIndex := 0

	for i := 0; i < len(nums); i++ {
		lengths[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] && lengths[j]+1 > lengths[i] {
				lengths[i] = lengths[j] + 1
				prev[i] = j
			}
		}
		if lengths[i] > maxLen {
			maxLen = lengths[i]
			maxIndex = i
		}
	}

	// Reconstruct LIS
	lis := []int{}
	for i := maxIndex; i >= 0; i = prev[i] {
		lis = append([]int{nums[i]}, lis...)
		if prev[i] == -1 {
			break
		}
	}

	return maxLen, lis
}

func main() {
	nums := []int{3, 1, 5, 2, 6, 4, 9}
	length, lis := longestIncreasingSubsequence(nums)
	fmt.Printf("Length of LIS: %d\n", length)
	fmt.Printf("Longest Increasing Subsequence: %v\n", lis)
}

for i := 0; i < len(nums); i++ {

iterate over each element to find LIS ending at i

lengths[i] = 1

each element alone is a subsequence of length 1

for j := 0; j < i; j++ {

check all previous elements to find smaller ones

if nums[j] < nums[i] && lengths[j]+1 > lengths[i] {

if nums[i] can extend subsequence ending at j and increase length

lengths[i] = lengths[j] + 1

update LIS length at i

prev[i] = j

record previous index for LIS reconstruction

if lengths[i] > maxLen {

update max LIS length and index

for i := maxIndex; i >= 0; i = prev[i] {

reconstruct LIS by following prev pointers backward

Output

Length of LIS: 4

Longest Increasing Subsequence: [1 2 4 9]

Complexity Analysis

Time: O(n^2) because for each element we check all previous elements to find increasing subsequences

Space: O(n) for storing lengths and previous indices arrays

vs Alternative: Naive approach tries all subsequences with exponential time; this dynamic programming approach is much faster

Edge Cases

empty list

returns length 0 and empty subsequence

DSA Go

if len(nums) == 0 {
	return 0, []int{}
}

all elements equal

LIS length is 1, subsequence is any single element

DSA Go

lengths[i] = 1

strictly decreasing list

LIS length is 1, subsequence is last element or any single element

DSA Go

lengths[i] = 1

When to Use This Pattern

When you need to find the longest sequence of increasing numbers in order without rearranging, use the Longest Increasing Subsequence pattern with dynamic programming.

Common Mistakes

Mistake: Not updating the previous index array to reconstruct the subsequence
Fix: Maintain a prev array to track the index of the previous element in the LIS for reconstruction

Mistake: Only calculating the length but not reconstructing the actual subsequence
Fix: Use the prev array to build the subsequence after computing lengths

Summary

Finds the longest increasing subsequence in a list of numbers.

Use when you want the longest ordered sequence of increasing values without changing order.

The key is to build lengths of LIS ending at each element and track previous elements to reconstruct the sequence.

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