longest-increasing-subsequence.go

// https://leetcode.com/problems/longest-increasing-subsequence
//
// [10,9,2,5,7,3,7,101,18]
// [a1,...aI-1] - LIS for I-1 elements
// why try to add aI element
// we should observe prev lengths from a1...aI-1 and choose the max length for aJ < aI, where J in [1, I-1]

func lengthOfLIS(nums []int) int {
    lenNums := len(nums)
    
    if lenNums == 0 {
        return 0
    }
    
    result := 1
    lengths := make([]int, lenNums)
    lengths[0] = 1
    
    for i := 1; i < lenNums; i++ {
        maxLength := 0
        
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                maxLength = max(lengths[j], maxLength)
            }
        }
        
        lengths[i] = maxLength + 1
        result = max(result, lengths[i])
    }
    
    return result
}

func max(a, b int) int {
    if a < b {
        return b
    }
    
    return a
}