Function lengthOfLIS

longest_increasing_subsequence_300/solution.go:6–33

Note: study again. Good dp problem.

(nums []int)

// Note: study again. Good dp problem.
func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	// dp[i] is equal to the length of the longest increasing
	// subsequence possible considering elements from [0,i)
	dp := make([]int, len(nums))
	dp[0] = 1

	maxResult := 1
	for i := 0; i < len(nums); i++ {

		// dp[i] = max(dp[j]) + 1, for j in [0,i), where nums[i] > nums[j]
		jMax := 0
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				jMax = int(math.Max(float64(jMax), float64(dp[j])))
			}
		}
		dp[i] = jMax + 1

		// set the final max result as we see new jMax
		maxResult = int(math.Max(float64(maxResult), float64(dp[i])))
	}

	return maxResult
}

func lengthOfLISOther(nums []int) int {
	if len(nums) == 0 {