문제

자연수로 이루어진 수열이 주어졌을 때 그 중에서 가장 길게 증가하는 원소들의 집합의 길이를 구하여라

입출력 예제

입력 : [5, 3, 7, 8, 6, 2, 9, 4]
출력 : 4

코드

function solution(arr) {
    let answer = 0;
    //  arr의 i 번째 숫자가 증가수열의 마지막 항이 되는 경우를 계산하였을 때 
    let dy = Array.from({length: arr.length}).fill(0)
    // 첫 번째 원소가 마지막 항이 될 경우 dy의 값은 무조건 1이다.
    dy[0] = 1
  // 두 번째 원소부터 차례로 확인했을 때 
    for(let i = 1; i < arr.length; i++ ) {
        let max = 0;
      // arr[i] 앞의 원소들을 for 문을 돌면서 확인하고
        for(let j = i - 1; j >= 0; j--) {
          // arr[i] 앞의 원소가 arr[i] 값보다 작고 + 앞에 있는 원소들의 값 중에 가장 큰 값을 찾아 
            if(arr[j] < arr[i] && dy[j] > max) {
                max = dy[j]
            }
        }
      // arr[i] 가 마지막 항이 될 경우를 추가하여 +1 한 값을 dy 배열에 넣는다.
        dy[i] = ++max
      // 그리고 리턴할 answer와 비교하여 큰 값을 찾는다. 
      	answer = Math.max(answer, dy[i])
    }
    return answer
}

console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]))	// 4