Four Segments
时间: 1ms 内存:128M
描述:
您将获得一个包含n个整数的数组。设sum(l,r)是区间[l,r)位置上所有数字的总和(计算第l个元素,不计算第r个元素)。0≤l≤r≤n。数组中的索引从0开始编号。
例如,如果a = [-5,3,9,4],则sum(0,1)= -5,sum(0,2)= -2,sum(1,4)= 16
选择三个界限符delim0,delim1,delim2(0≤delim0≤delim1≤delim2≤n)和以这样的方式划分阵列的值res = sum(0, delim0) - sum(delim0, delim1) + sum(delim1, delim2) - sum(delim2, n)。让res的值最大。
输入:
第一行包含一个整数n(1≤n≤5000).
第二行包含n号码一个a0, a1, ..., an-1 (-10^9≤ai≤10^9).
输出:
选择的三个界限符,使res的值最大。如果有多个答案,请打印字典序最小的。
示例输入:
3
-1 2 3
示例输出:
0 1 3
提示:
参考答案:
文章评论