문제

https://www.acmicpc.net/step/11054

풀이

	let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
    let N = +input[0]
    let arr = input[1].split(' ').map(Number)
    
    let upDP = new Array(N).fill(0)  ---------------- (1)
    let downDP = new Array(N).fill(0)
    
    upDP[0]= 1;
    downDP[N]=1;

    for(let i=1; i<N; i++){ ---------------- (2)
      let cnt = 1;
      for(let j=0; j<i; j++){
        if(arr[j] < arr[i]) cnt = Math.max(cnt,upDP[j]+1)
      }
      upDP[i]= cnt;
    }

    for(let i=N-1; i>=0; i--){ ---------------- (3)
      let cnt = 1;
      for(let j=i+1; j<=N; j++){
        if(arr[j] < arr[i]) cnt = Math.max(cnt,downDP[j]+1)
      }
      
      downDP[i] = cnt;
    }
    
	console.log(Math.max(...upDP.map((ele,idx)=>ele+downDP[idx]))-1)

LIS를 변형한 문제였는데 양쪽으로 증가하는 수열을 검사해야하는 문제였다. 앞쪽에서 증가하는 수열의 DP와 뒷쪽에서 증가하는 수열을 각각 구해서 각 항에서 나올 수 있는 갯수를 다 더해서 최댓값을 구하는 방식이다. 그래서 1번에서 arr[0]부터 시작하는 upDP와 arr[N]부터 시작하는 downDP를 만들어준다.
이후에는 2번에서 arr[0]부터 시작해서 LIS와 같은 형식으로 자기보다 큰 수를 연속해서 이어나가는 갯수를 upDP에 저장해두고 3번에서는 arr[N]부터 시작해서 아래로 내려가면서 갯수를 구해준다.
3번에서 구한 두 dp배열의 합을 구해서 그 배열의 최댓값에서 -1을 빼준다. -1을 해준 이유는 앞과 뒤로 탐색을 수행하면서 한번씩 겹치기 때문에 -1을 해주어야한다.