是否可以从其前缀和后缀和中找到整数的原始序列？

Question

是否有办法从initial sequence和prefix sums中找到suffix sums？

在i位置的前缀和是从开始到i位置的所有元素的和。

第i位的后缀总和是从最后到第i位的所有元素的总和以相反的顺序。

例如，组合的[prefix sums和suffix sums]序列如下：

{1, 3, 3, 5, 6, 6}

initial sequence是：{1, 2, 3}

[Prefix sums：{1, 3, 6}，Suffix sums：{6, 5, 3}

合计：{1, 3, 3, 5, 6, 6}

在某些情况下可能有多种可能性。

Answer 1

前缀总和：

---

  original array : {1, 2, 3}
  prefix sum array : {1, 1+2, 1+2+3}

后缀和：

---

  original array : {1, 2, 3}
  suffix sum array : {3+2+1, 3+2, 3}

根据您的问题，组合数组似乎已排序。因此

---

 Let combined array be c[] = {1, 1+2, 3, 3+2, 1+2+3, 3+2+1} = {1, 3, 3, 5, 6, 6}

现在，找到原始序列：

1. 如果原始数组具有n个元素，则组合数组将具有2 * n个元素
2. [像array1 = {c [0]，c [2]，c [4]}和array2 = {c [1]，c [3]，c [5]}分割数组
3. array1现在将具有前缀和，而array2将具有后缀和
4. 现在array1足以找到原始序列（因为组合数组已排序根据您的问题）。因此，原始数组将为{c [0]，c [2] -c [0]，c [4] -c [2]}

---

int length = combined_array.length/2;
int []prefix_breakup = new int[length];
int []original = new int[length];

for(int i=0; i<length ; i++){
    if( i%2 == 0 ){
        prefix_breakup[i] = combined_array[i];
    } 
}

original[0] = prefix_breakup[0];

for(int i=1; i<length ; i++){
    original[i] = prefix_breakup[i] - prefix_breakup[i-1];
}

Answer 2

如果我们只取总和等于前缀总和的那对呢？然后计算那些给定对的排列，即我们可以从每对中选择一个元素，然后获得所需的序列。

例如

5 6 7 10 10 5 3 4
Prefix sum array : 5 6 7 10/5 3 4 10
Suffix sum array :5 3 4 10/5 6 7 10

Prefix final sum = 10
The pairs are (6,4),(7,3),(5,5)
We can choose, 6 7 5
or 4 3 5
or 4 7 5 and so on.

所需的排列，以便我们从每对中选择一个元素基本上是2 * 2 * 1 * 3!，即24。

Prefix final sum = 10
Eg : 5 7 10 3 5 10
Prefix sum array : 5 3 10/5 7 10
Suffix sum array : 5 7 10/5 3 10

对是(5,5), (7,3)

所需的排列是1*2*2!，即4。

有人可以向我解释我要去哪里错吗？因为这给了WA。