It is considered an array of a[1], a[2], …, a[n] of nonzero natural numbers. For two indices 1 ≤ i <j <n, we note with X = a [1] + a [2] + … + a [i], Y = a [i + 1] + a [i + 2] + … + a [j] and Z = a [j + 1] + a [j + 2] + … + a [n].
Determine two indices i and j so that the difference max (X, Y, Z) - min (X, Y, Z) is minimal.
I need an O(nlogn) solution. This problem is from another website.
Could you please post the link to the question?
3 Likes
Is the array sorted?
What’s the maximum size that the array can be?
Can you share a link to the original question?
This is not in English.
1 ≤ n ≤ 200 000
-
1 ≤ a[i] ≤ 10 000
The array is not sorted. You need to use partial sums in vector.
The time limit is 0.2 seconds