백준 14180 - 배열의 특징 (C++)

문제 문제 링크 BOJ 14180 - 배열의 특징 문제 요약 배열의 특징이 $C = ΣAi·i (1 ≤ i ≤ n)$로 정의된다. 배열에서 수 하나를 아무 위치로 이동시킬 수 있을 때, 가능한 $C$의 최댓값을 구해보자.

제한 TL : $2$ sec, ML : $512$ MB $2 ≤ N ≤ 200,000$ $|A_i| ≤ 1,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 누적 합(prefix_sum) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 임의의 인덱스 $i$를 기점으로 배열을 나눠 왼 쪽, 오른 쪽 인덱스로 이동한다고 생각해보자. 왼 쪽으로 이동 한다고 할 때.

이동 시 변화를 파악하기 위해 간단한 예를 하나 들겠다. 배열 $a_n$ = { $a_1, a_2, a.....