东东每个学期都会去寝室接受扫楼的任务,并清点每个寝室的人数。 每个寝室里面有 ai 个人(1 ≤ i ≤ n)。从第 i 到第 j 个宿舍一共有 sum(i, j) = a[i] + ... + a[j] 个人 这让宿管阿姨非常开心,并且让东东扫楼 m 次,每一次数第 i 到第 j 个宿舍 sum(i, j) 问题是要找到 sum(i1, j1) + ... + sum(im, jm) 的最大值。且 ix ≤ iy ≤ jx 和 ix ≤ jy ≤ jx 的情况是不被允许的。也就是说 m 段都不能相交。 注:1 ≤ i ≤ n ≤ 1e6, -32768 ≤ ai ≤ 32767 人数可以为负数。(1 ≤ n ≤ 1000000)
|