Finding the Longest Increasing Subsequence in Go

In this example, we will write a Go program to find the longest increasing subsequence (LIS) in a given array. The LIS is a subsequence of a sequence in which the elements are in sorted order, but not necessarily contiguous. The goal is to find the longest such subsequence.

Program Structure and Explanation

The Go program to find the LIS uses dynamic programming. The approach is to maintain an array where each entry at index i represents the length of the longest increasing subsequence that ends at index i.

Algorithm

1. Create an array lis where lis[i] will store the length of the longest increasing subsequence ending with arr[i].
2. Initialize each entry in lis to 1, as the minimum length of LIS ending at each element is 1 (the element itself).
3. For each element arr[i], compare it with all previous elements arr[j] (where j < i). If arr[j] < arr[i], update lis[i] as lis[i] = max(lis[i], lis[j] + 1).
4. The result is the maximum value in the lis array.

Go Program

package main

import "fmt"

// Function to find the longest increasing subsequence
func longestIncreasingSubsequence(arr []int) int {
    n := len(arr)
    if n == 0 {
        return 0
    }

    // Create an array to store the length of LIS ending at each index
    lis := make([]int, n)
    for i := range lis {
        lis[i] = 1
    }

    // Compute LIS values in a bottom-up manner
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ { if arr[i] > arr[j] && lis[i] < lis[j]+1 {
                lis[i] = lis[j] + 1
            }
        }
    }

    // Find the maximum value in lis
    maxLis := 0
    for _, length := range lis {
        if length > maxLis {
            maxLis = length
        }
    }

    return maxLis
}

func main() {
    // Example array
    arr := []int{10, 22, 9, 33, 21, 50, 41, 60, 80}
    
    // Find the length of the longest increasing subsequence
    result := longestIncreasingSubsequence(arr)
    
    // Print the result
    fmt.Printf("Length of Longest Increasing Subsequence: %d\n", result)
}

Program Documentation

Function: longestIncreasingSubsequence(arr []int) int

This function takes an array of integers arr as input and returns the length of the longest increasing subsequence.

• Input: An array of integers.
• Output: An integer representing the length of the longest increasing subsequence.

Function: main()

The main function demonstrates how to use the longestIncreasingSubsequence function. It initializes an example array, calls the function, and prints the result.