구간차의 합 최대

예를 들어 설명하겠습니다.

7 개의 데이터가 있고 데이터가 다음과 같다면

6 2 9 8 3 4 7

다음과 같이 하는것이 최대 입니다.

6 2 9 8 3 4 7
----- --- ---
  7    5   3

점화식 dy[i][j] 정의하면

• i~j 에서의 구간차의 합의 최대 값으로 놓겠습니다.
• 답은 dy[1][7]

입니다.

일단 눈으로 다음과 같이 채웁니다.

dy[1][3] 은 6 2 9 에서 최대 최소의 차는 7 dy[4][6] 은 8 3 4 에서 최대 최소의 차 5.

dy[1][4]에서 생각해 보겠습니다.

• (1 - 4) ... O(n) 으로 계산
• (1 - 2) + (3 - 4) 는 기존의 테이블에서 참조

중 최대 값 입니다.

dy[1][7] 은

• (1 - 7) .. O(n)
• (1 - 5) + (6 - 7)
• (1 - 4) + (5 - 7)
• (1 - 3) + (4 - 7)
• (1 - 2) + (3 - 7)

중 최대 값 입니다.

일반화 해서 점화식을 세워보면

dy[i][j] = max( data[i]~data[j]의 최대/최소의 차 , dy[i][k] + dy[k+1][j] ,단 k = i+1 ... j-1 )

시간 복잡도

O(n^3)

출처: dovelet