문제

수열

풀이

해당 풀이는 DP로 풀면 됩니다. DP 배열에는 현재 인덱스까지 이전값과 같거나 높은 값을 저장하는 방식으로 구현합니다. 거꾸로 수열이 이뤄지는 경우도 계산해야 하기 때문에 배열을 두개를 선언해야 합니다.

			if (arr[i - 1] <= arr[i]) {
                dp[i] = Math.max(dp[i], dp[i - 1] + 1);
            }
            if (arr[i - 1] >= arr[i]) {
                dp2[i] = Math.max(dp2[i], dp2[i - 1] + 1);
            }

해당 배열에서 가장 큰 값이 되는 수를 리턴하면 됩니다. 그리고 이 값에 +1을 해야하는데, 그 이유는 처음 수열이 시작하는 원소는 더해주지 않은 값이기 때문입니다.

DP로 먼저 문제를 생각하는 버릇이 안들어져 있어서 어려웠습니다.

전체 코드

전체 코드