Longest Increasing Subsequence

1. Problem Description

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array by deleting (or not deleting) some elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of [0,3,1,6,2,2,7].

2. Approach

1. Approach 1
   • DFS
   • For each element, try adding it to the increasing subsequence; if a larger element can be found later, continue searching
2. Approach 2
   • DFS + memoization

3. Implementation

3.1. DFS

func lengthOfLIS(nums []int) int {
	count := 0
	maxCount := 0

	lengthOfLISDFS(nums, 0, &count, &maxCount)
	return maxCount
}

func lengthOfLISDFS(nums []int, index int, count *int, maxCount *int) {
	for i := index; i < len(nums); i++ {
		if (nums[i] > nums[index] || *count == 0) && len(nums)-i+*count > *maxCount {
			*count++
			*maxCount = Max(*maxCount, *count)

			lengthOfLISDFS(nums, i, count, maxCount)

			*count--
		}
	}
}

3.2. DFS + Memoization

func lengthOfLIS(nums []int) int {
    memo := make(map[[2]int]int, 0)

    return lengthOfLISDFS(nums, 0, math.MinInt32, memo)
}

func lengthOfLISDFS(nums []int, index int, prev int, memo map[[2]int]int) int {
    key := [2]int{index, prev}
    count, ok := memo[key]
    if ok {
        return count
    }

    if index >= len(nums) {
        return 0
    }


    for i := index; i < len(nums); i++{
        if nums[i] > prev {
            count = max(count, 1+lengthOfLISDFS(nums, i+1, nums[i], memo))
        }
    }

    memo[key] = count
    return count
}

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

    return b
}

4. References

• 300. Longest Increasing Subsequence - LeetCode