editorial

D

summary:

배열 $a$에서 임의의 원소 $i_0, \dots, i_k$들을 골라서 구간을 막은 뒤, $max([a_0, a_{i_0-1}], [a_{i_0+1}, a_{i_1-1}], \dots, [a_{i_{k-1}+1}, a_{i_k}], [a_{i_k+1}, a_n], a_{i_0}+a_{i_1}+\dots+a_{i_k})$을 구하는 문제이다.

solution:

기본 솔루션은 이분탐색이다. $mid$보다 정답이 작거나 같을 수 있는가? 를 묻는 것인데, $d_i=$ $i$인덱스까지, $i$인덱스를 막은 원소에 포함시켰을 때 막은 원소의 총합의 최솟값이다.

set에 넣어서 풀면 된다.