BOJ 2491

Input

첫째 줄에는 수열의 길이 N이 주어지고,

둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다.

N은 1 이상 100,000 이하의 정수이다.

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))

Output

첫째 줄에 가장 긴 길이를 출력한다.

if index == N-1:
  print(max(map(max, increment, decrement)))
  return

DP

체크해야 할 경우는 2가지인데,

1. 연속해서 증가하는 경우
2. 연속해서 감소하는 경우

위 2가지 중 더 긴 수열의 길이를 출력하면 된다.

따라서 default로 길이가 본인의 길이인 1로 초기화된 배열을 2개 생성하고,

increment = [1]*N
decrement = [1]*N

재귀함수를 정의한다.

• break point: index가 끝에 도달하면 max 값을 출력한다.

  if index == N-1:
    print(max(map(max, increment, decrement)))
    return

• 연속해서 증가하는 경우: increment 배열에 그 전까지의 길이+1 를 append 한다.

  if num[index + 1] >= num[index]:
    increment[index+1] += increment[index]

• 연속해서 감소하는 경우: decrement 배열에 그 전까지의 길이+1 를 append 한다.

  if num[index + 1] <= num[index]:
    decrement[index+1] += decrement[index]

• 진행하기 위해서 재귀 함수를 호출한다.

  return lengthen(index+1)

• 첫 시작을 위해서,

  lengthen(0)