#2376 포켓몬의 세계 [part3-1. powerful Mr.J][easy-mode]

20 s   128 MB  

Description

포켓몬 세계에서 제 1구역의 왕은 Mr.J(이름하여 미스터 제이)이다.

어느날 2구역의 농민 Mr.A가 1구역에 들어왔다가,

Mr.J를 보고만다. 그러다가 갑자기 그의 파워가 궁금하게 됬다. 하지만 역시 1구역의 왕 답게

농민인 Mr.A가 그의 힘을 알기에는 너무 어려웠다.

그러다가 결국 Mr.M에게 도움을 요청한다. Mr.M은 소문난 코더다. 

 

Mr.J의 파워를 나타내는 정수가 $N$개만큼 들어온다.

 

그리고 그 정수들을, $K$개로 나누어야한다(물론 연속적으로)

 

$|p_1-p_2| + |p_2-p_3| + \dots + |p_k-1 - p_k|$ 의 maximum value $=$ Power of Mr.J

 

여기서 $p_x$ 는 subarray x의 합. 

 

sample input/output을 확인해보면,

[5] [2, 4, 3] [1]

 

$p_1$ = 5, $p_2$ = 9, $p_3$ = 1

 

그래서 Mr.J의 파워는 $4 + 8 = 12$ 

Input

$N$ $(2 \leq N \leq 400)$ $K$ $(4 \leq K \leq 50)$ 단, $(K \leq N)$

입력되는 정수 $Xi(i=1 \dots n)$ $(1 \leq Xi \leq 5000)$

Sample Input

Sample Output

5 3
5 2 4 3 1
12

Source

wowoto9772