최대 부분 증가수열

코드

  function solution(arr) {
    let answer = 0;
    let dy = Array.from({ length: arr.length }, () => 0);
    dy[0] = 1;

    for (let i = 1; i < arr.length; i++) {
      let max = 0;
      for (let j = i - 1; j >= 0; j--) {
        if (arr[i] > arr[j]) max = Math.max(dy[j], max);
      }
      dy[i] = max + 1;
    }

    answer = Math.max(...dy);
    console.log(dy);

    return answer;
  }

해결 방법

맨 처음있는 5까지만 본다치면 최대 길이는 1이다.

두번째 3은 첫번째 5 다음으로 올 수 없어서 최대 길이는 1이다.

세번째 7은 자기보다 작고 앞에 있는 배열의 최대 길이에서 +1을 해주면된다. 네번째 8도 마찬가지다.

다섯번째 6은 자기보다 작고 앞에 있는 배열의 최대 길이가 1이라서 최대 길이가 2이다.