Why Longest Increasing Subsequence in DSA Go?

The Big Idea

Discover how to find the longest rising pattern in a sea of numbers without getting lost!

The Scenario

Imagine you have a list of daily temperatures, and you want to find the longest period where the temperature keeps rising every day. Doing this by checking every possible sequence manually would be like trying to find a needle in a haystack.

The Problem

Manually checking all possible increasing sequences is slow and confusing. It takes too long and you can easily miss the longest one or make mistakes counting. This gets worse as the list grows longer.

The Solution

The Longest Increasing Subsequence (LIS) method quickly finds the longest rising sequence without checking every possibility. It uses smart steps to remember and build the best sequences as it goes, saving time and effort.

Before vs After

✗ Before

for i := 0; i < len(arr); i++ {
  for j := i + 1; j < len(arr); j++ {
    // check if arr[j] > arr[i] and track sequences
  }
}

✓ After

lengths := make([]int, len(arr))
for i := range arr {
  lengths[i] = 1
  for j := 0; j < i; j++ {
    if arr[j] < arr[i] && lengths[j]+1 > lengths[i] {
      lengths[i] = lengths[j] + 1
    }
  }
}

What It Enables

This lets you find the longest rising pattern in data fast, helping with tasks like trend analysis, stock prices, or game scores.

Real Life Example

In stock trading, finding the longest increasing subsequence of prices helps identify the longest period of growth, guiding better investment decisions.

Key Takeaways

Manual checking is slow and error-prone.

LIS uses smart memory to find the longest rising sequence efficiently.

It helps analyze trends and patterns in many real-world data sets.

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