CF846C Four Segments

给定一个长度为 $n$ 的整数数组。定义 $sum(l,r)$ 为下标从 $l$ 到 $r-1$（包括 $l$，不包括 $r$）位置上所有元素的和。$l$ 与 $r$ 满足 $0 \leq l \leq r \leq n$。数组下标从 $0$ 开始编号。 例如，若 $a=[-5,3,9,4]$，则 $sum(0,1) = -5$，$sum(0,2) = -2$，$sum(1,4) = 16$，对于每个 $i$（$0 \leq i \leq 4$）都有 $sum(i,i)=0$。 请选择三个分割点（$delim_0$、$delim_1$、$delim_2$），其中 $0 \leq delim_0 \leq delim_1 \leq delim_2 \leq n$，将数组分为四段，使下式的值 $res = sum(0, delim_0) - sum(delim_0, delim_1) + sum(delim_1, delim_2) - sum(delim_2, n)$ 取得最大值。 注意，一些 $sum(l,r)$ 可能对应于空区间（当 $l=r$ 时）。

第一行包含一个整数 $n$（$1 \leq n \leq 5000$）。 第二行包含 $n$ 个整数 $a_0, a_1, ..., a_{n-1}$（$ -10^9 \leq a_i \leq 10^9$）。

请输出三个下标，使 $res$ 的值最大。如果有多组答案，输出任意一组均可。

由 ChatGPT 5 翻译