[BOJ] 14240번: 부분 수열의 점수

https://www.acmicpc.net/problem/14240

$A_i = s_1+s_2+...+s_i$라고 하면, 수열 $(s_i, s_(i+1), ..., s_j)$의 합을 $(A_j-A_(i-1)) + (A_j-(A_i)) + ... + (A_j-(A_j-1))$로 표현할 수 있고, 더 나아가 $B_i = A_1+A_2+..+A_i$라고 한다면 최종적으로 $A_j * (j-i+1) - (B_(j-1)-B_(i-2))$로 나타낼 수 있습니다.

이제 $D_k$를 k를 수열의 끝으로 하는 수열 중의 최댓값이라고 한다면,

$D_k = \max (j *(-A_k) + B_(j-2))+A_k*(k+1-b_(k-1))$ 로 변형할 수 있습니다. $max(0,D[1],D[2],D[3],...,D[N])$이 정답이고, 저 수식에서 기울기($j$)가 증가하므로 Convex Hull Trick을 사용해 $O(NlgN)$ 에 해결할 수 있습니다. 구현 상으로는, 제가 가진 class가 기울기가 감소할 때에 대한 class여서 구현의 편의를 위해 $A_i$를 전부 부호를 반전시키고, 기울기를 $-j$로 생각해 기울기가 감소하도록 만들었습니다.

https://github.com/blisstoner/BOJ/blob/master/14240.cpp