arr[6] = {10, 20, 30, 25, 20} 를 예시로 들어보겠습니다.

  1. 맨 앞에서 부터 element에 접근할 건데, 뭔가 dp[0] 은 1이 들어갈 것 같고, dp[1]은 dp[0]에서 구한 값의 합을 더하긴 하는데... 분기를 두면 될거 같고..
  2. 앞에서 부터 증가하고 뒤에서 부터 증가하는 거니까 increase 배열을 따로 두고 decrease 배열을 따로 둬서 계산하면 될 것 같은데.. ?

부분 수열하니 생각나는 것이 LCS (최장 공통 부분 수열) 입니다. 따라서 그림을 그려가며 생각을 해봅니다.

       10 20 30 25 20

        0    0  0   0   0

10 0

20 0

30 0

25 0

20 0

LCS처럼 생각해서 그림을 그린 후에 똑같이 접근해 봅니다.