题解 | #71.最长上升子序列(一)#

状态转移方程

$dp[i]=Math\mathrm{.}max(dp[i],dp[j]+1)dp[i]\; =\; Math.max(dp[i],dp[j]+1)$ 条件：

function LIS( arr ) {
  if(arr.length == 0)
    return 0;
  
  let dp = new Array(arr.length);
  dp[0] = 1;
/* 
*遍历数组中所有的数，再遍历当前数之前的所有数，
*只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变，取两者中的较大者。
*即dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)dp[i]=Math.max(dp[i],dp[j]+1)
*/ 
  for(let i=1; i<arr.length; i++){
    dp[i] = 1;
    for(let j=0; j<i; j++){
      if(arr[i] > arr[j])
        dp[i] = Math.max(dp[i],dp[j]+1);
    }
  }
  
  return Math.max(...dp);
}