算法训练营 Day 52 | 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

[KoEkko]

300.最长递增子序列

dp数组的含义是：dp[i]就是以nums[i]为结尾的最长递增子序列的个数。
我们知道dp[i]可以由前面的状态dp[i-x]推导出来，前提是 num[i] 得大于其中某个数，才能够进行累加。
所以dp[j]就是用来判断之前的某个状态是否符合条件，再进行累加。
其中+1就是+上本身的长度1，dp[j]是之前的状态。

function lengthOfLIS(nums:number[]):number {
  const dp: number[] = new Array(nums.length).fill(1);
  let result:number = 0;
  for(let i = 1; i < nums.length; i++) {
    for(let j = 0 ; j < i; j++) {
      if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j]+1);
    }
    result = Math.max(result, dp[i])
  }
  return result;
}

674. 最长连续递增序列

dp[i]以nums[i]为结尾的最长连续递增子序列的长度。因为是连续的，所以，只有在 nums[i] > nums[i -1]的时候，才需要更新dp[i]的值。

function findLengthOfLCIS(nums: number[]): number {
  const dp: number[] = new Array(nums.length).fill(1);
  let result = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;
    result = Math.max(result, dp[i]);
  }
  return result;
}

718. 最长重复子数组

function findLength(nums1: number[], nums2: number[]): number {
  const dp: number[][] = new Array(nums1.length + 1)
    .fill(0)
    .map((_) => new Array(nums2.length + 1).fill(0));
  let result = 0;
  for (let i = 1; i <= nums1.length; i++) {
    for (let j = 1; j <= nums2.length; j++) {
      if (nums1[i - 1] === nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
      result = Math.max(result, dp[i][j]);
    }
  }
  return result;
}