Longest Increasing Subsequence

Problem statement

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps relative order but need not be contiguous.

Example:

Input:

nums = [10, 9, 2, 5, 3, 7, 101, 18]

Expected output:

4

Why: one LIS is [2, 3, 7, 101] (length 4).

Practice on LeetCode: Longest Increasing Subsequence

Golang Solution

dp[i] is the longest increasing subsequence that ends at index i. For each i, try every earlier j with nums[i] > nums[j] and take dp[j] + 1. The answer is the max over dp.

Time: O(n²)
Space: O(n)

func lengthOfLIS(nums []int) int {

    if len(nums) <= 1 {
        return len(nums)
    }

    dp := make([]int, len(nums))
    dp[0] = 1

    for i := 1; i < len(nums); i++ {
        dp[i] = 1
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }

    maxVal := math.MinInt
    for _, val := range dp {
        if maxVal < val {
            maxVal = val
        }
    }

    return maxVal
}