最长递增子序列

300. 最长递增子序列

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i] 表示以 nums[i] 为结尾的数组的最大递增子序列长度为 dp[i]。

2.初始化 dp 数组，dp[i] = 1。

3.确定遍历方向，从前往后遍历 i，然后再从 0 遍历到 i - 1。

4.确定转移方程：当 nums[i] > nums[j] 时，位置为 i 的最长递增子序列长度为从 0-i 位置的最长子序列长度 + 1，即取 dp[i] 和 dp[j] + 1 的最大值。

5.将 dp 数组中的最大值返回即可。

typescript 解法

function lengthOfLIS(nums: number[]): number {
  const length: number = nums.length;
  // 确定dp数组含义：dp[i]表示以nums[i]为结尾的数组的最大递增子序列长度为dp[i]
  // 初始化dp数组：默认为1
  const dp: number[] = new Array(length).fill(1);
  let maxLength: number = 1;
  // 确定遍历方向：从前往后遍历i，然后再从0遍历到i-1
  for (let i: number = 1; i < length; i++) {
    for (let j: number = 0; j < i; j++) {
      // 确定转移方程：当nums[i]>nums[j]时，位置为i的最长递增子序列长度为从0-i位置的最长子序列长度+1，即取dp[i] 和dp[j] + 1 的最大值。
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    if (dp[i] > maxLength) {
      maxLength = dp[i];
    }
  }
  return maxLength;
}

go 解法

func lengthOfLIS(nums []int) int {
    length := len(nums)
    // dp表示以nums[i]结尾数组的最长递增子序列长度
    dp := make([]int, length)
    // 初始化dp数组
    for i := 0; i < length; i ++ {
        dp[i] = 1
    }
    maxLength := 1
    // 确定遍历方向
    for i := 1; i < length; i ++ {
        for j := 0; j < i; j ++ {
            // 确定转移方程：当nums[i] 大于nums[j]时，则位置为i的最长递增子序列长度为从0-i位置的最长子序列长度+1
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
        if dp[i] > maxLength {
            maxLength = dp[i]
        }
    }
    return maxLength
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}