Longest Increasing Subsequence in DSA Go - Build from Scratch

Longest Increasing Subsequence

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

🎯 Goal: Build a Go program that finds the length of the longest increasing subsequence in a list of stock prices.

📋 What You'll Learn

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

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

Create a slice of integers called lis of length n initialized with 1s

Use nested for loops with variables i and j to compute the longest increasing subsequence lengths

Create an integer variable called maxLength to track the maximum LIS length

Print the value of maxLength

💡 Why This Matters

🌍 Real World

Finding the longest increasing subsequence helps analyze trends in stock prices, sales data, or any time series where growth periods are important.

💼 Career

Understanding this algorithm is useful for software engineers working on data analysis, financial software, or any application involving sequence pattern recognition.

1

Create the prices slice

Create a slice of integers called prices with these exact values: 10, 22, 9, 33, 21, 50, 41, 60

DSA Go

package main

func main() {
    // Create the prices slice with the given values
    // Your code here
}

Hint

Use prices := []int{...} to create the slice with the exact numbers.

2

Initialize helper variables

Create an integer variable called n that stores the length of prices. Then create a slice of integers called lis of length n where each element is initialized to 1

DSA Go

package main

import "fmt"

func main() {
    prices := []int{10, 22, 9, 33, 21, 50, 41, 60}
    // Create n as length of prices
    // Create lis slice of length n with all elements 1
    // Your code here
}

Hint

Use len(prices) to get the length. Use make([]int, n) to create the slice. Use a for loop to set each element to 1.

3

Compute the longest increasing subsequence lengths

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 the inner loop, if prices[i] is greater than prices[j] and lis[i] is less than lis[j] + 1, then update lis[i] to lis[j] + 1. Then create an integer variable called maxLength and set it to the maximum value in lis

DSA Go

package main

import "fmt"

func main() {
    prices := []int{10, 22, 9, 33, 21, 50, 41, 60}
    n := len(prices)
    lis := make([]int, n)
    for i := 0; i < n; i++ {
        lis[i] = 1
    }
    // Use nested loops to update lis values
    // Create maxLength variable and find max in lis
    // Your code here
}

Hint

Use two for loops to compare each pair. Update lis[i] when you find a longer subsequence. Then find the maximum value in lis by checking each element.

4

Print the longest increasing subsequence length

Print the value of maxLength using fmt.Println(maxLength)

DSA Go

package main

import "fmt"

func main() {
    prices := []int{10, 22, 9, 33, 21, 50, 41, 60}
    n := len(prices)
    lis := make([]int, n)
    for i := 0; i  prices[j] && lis[i]  maxLength {
            maxLength = lis[i]
        }
    }
    // Print maxLength
    // Your code here
}

Hint

Use fmt.Println(maxLength) to print the final 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 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