최대 부분 증가수열 : Dynamic Programming

내 풀이

내풀이1 - 잘못된 풀이

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let check = Array.from({ length: arr.length }, () => false);
  for (let i = 0; i < arr.length; i++) {
    if (!check[i]) {
      let tmp = arr[i];
      let cnt = 1;
      for (let j = i + 1; j < arr.length; j++) {
        if (tmp < arr[j]) {
          tmp = arr[j];
          check[j] = true;
          cnt++;
        }
      }
      answer = Math.max(answer, cnt);
    }
  }
  return answer;
}

let arr = [5, 3, 7, 8, 6, 2, 9, 4];
console.log(solution(arr));

이미 체크한 요소는 더이상 확인하지 않도록 진행했는데 부분수열이 겹치는 경우도 있지 않은가? 에 대해 조금 더 생각해봐야 할 것 같다

내풀이2 - 수정된 풀이

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let dy = Array.from(arr).fill(1);
  dy[0] = 1;
  for (let i = 1; i < arr.length; i++) {
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] < arr[i]) {
        dy[i] = Math.max(dy[j] + 1, dy[i]);
        answer = Math.max(answer, dy[i]);
      }
    }
  }
  return answer;
}

let arr = [5, 3, 7, 8, 6, 2, 9, 4];
console.log(solution(arr));

Dynamic Programming 설명을 듣고 코드를 짜 보았다

Solution 풀이

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[j] < arr[i] && dy[j] > max) {
        max = dy[j];
      }
    }
    dy[i] = max + 1;
    answer = Math.max(answer, dy[i]);
  }
  return answer;
}

let arr = [5, 3, 7, 8, 6, 2, 9, 4];
console.log(solution(arr));

수정된 풀이랑 비슷하지만

• if 문에 and 조건을 넣어주는 것
• 마지막에 max + 1 과 answer 을 업데이트 해 주는 점이 조금 더 코드가 간결하면서 직관적인 것 같다.