Is there a way to find the initial sequence from its prefix sums and suffix sums?
Prefix sum at i
th position is the sum of all elements from beginning to i
th position.
Suffix sum at i
th position is the sum of all elements from last to i
th position in reverse order.
For an example, the combined (prefix sums and suffix sums) sequence is as follows:
{1, 3, 3, 5, 6, 6}
The initial sequence was: {1, 2, 3}
Prefix sums: {1, 3, 6}
, Suffix sums: {6, 5, 3}
In combined: {1, 3, 3, 5, 6, 6}
May be in some cases there are multiple possibilities.
Prefix Sum:
Suffix Sum:
As per your question, the combined array seems to be sorted. Therefore
Now, finding the original sequence: