링크

14002 가장 긴 증가하는 부분 수열 4

문제

풀이

이 문제는 예전에 풀었던 가장 긴 증가하는 부분 수열 시리즈랑 비슷했다.

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

처음에 현재값을 기준으로 이전값들을 비교한다. 그리고 만약 현재값이 이전값보다 크면 그 dp[현재인덱스]에다가 dp[이전값인덱스] + 1과 dp[현재인덱스]를 비교해서 dp 배열을 만들어준다.

그리고나서 가장 큰 maxIdx값을 가지고 dp배열의 맨 마지막에서 쭉 탐색하면서 maxIdx의 값과 같으면 stack에 넣고 maxIdx-- 해주고 마지막엔 stack을 다 빼면 된다.