LeetCode 300번

nums 라는 배열이 주어지면 그 안에서 가장 긴 증가하는 부분배열을 찾는 문제이다.

dp 문제에 속해 있어 어떻게 풀 지 계속 고민해보다가 도저히 해결방법을 생각하지 못해 풀이를 참고하였다

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

먼저 nums배열과 길이가 같은 dp 배열 하나를 만들어준다.
그리고 모두 1로 값을 셋팅해준다.

dp[i] 를 i번째까지 가장 긴 증가 부분배열의 길이라고 생각을 하면 된다.

i가 1에 있을때는 j가 0까지 순환할 거고
nums[0] 과 nums[1]의 크기를 비교해준다. 만일 numx[0]의 크기가 작으면 nums[0] nums[1] 이렇게 증가부분배열의 길이가 2가 되므로 갱신을 해준다.

그럼 Math.max(dp[i],1+dp[j]) 이 부분은 왜 해준걸까?

예를 들어 [10,9,2,5,3,7,101,18]을 생각해 보자.

i= 1 ==> [1,1,1,1,1,1,1,1]
i= 2 ==> [1,1,1,1,1,1,1,1]
i= 3 ==> [1,1,1,2,1,1,1,1]
// 여기서 nums[3]은 nums[2]보다 크므로 갱신된다.
i= 4 ==> [1,1,1,2,2,1,1,1]
// 여기서 j가 2일때 nums[j] 와 nums[i]중 nums[i]가
크므로 갱신된다.
i= 5 ==> nums[i] = 7이다.
j= 0 ==> 10 > 7 이므로 갱신 x
j= 1 ==> 9 > 7 이므로 갱신 x
j= 2 ==> 2 < 7 ==> dp[2] 와 1+dp[5] 비교
dp[5]가 2로 갱신 된다.

j =3 ==> 5 < 7 ==> dp[3] 와 1+dp[5] 비교
dp[5]가 3으로 갱신 된다.

이렇게 2, 7 인 형태로 부분증가배열이 생길 수 있고
또한 2,3,7 형태로 부분증가 배열이 생길 수 있는데
위의 코드는 가장 긴 부분증가 배열을 찾는 것이므로 max를 써서
더 큰 값으로 갱신을 해주는 것 같다.