对于一个长度为n的数组 a[0]∼a[n−1]，它的前缀和 sum[i] 等于 a[0]∼a[i] 的和。例如：

• sum[0] = a[0]
• sum[1] = a[0] + a[1]
• sum[2] = a[0] + a[1] + a[2]
• ⋯

        利用递推，只要计算 n 次，就能计算出所有的前缀和：sum[i] = sum[i-1] + a[i]。当然，我们也能用 sum[] 反推计算出 a[]：a[i] = sum[i] - sum[i-1]。

如果预先算出了前缀和，这时想知道 a[i]∼a[j] 的和，可以用sum[j]−sum[i−1]。 可以利用前缀和快速计算出数组中任意一个区间的和。本来复杂度为 O(n)的区间和计算，优化到了 O(1) 的前缀和计算。

第一题 灵能传输

 

样例输入

3
3
5 -2 3
4
0 0 0 0
3
1 2 3

样例输出

3
0
3

 

import java.util.*;public class Main {public static void main(String[] args) {Scanner cinScanner = new Scanner(System.in);int T;T = cinScanner.nextInt();while (T != 0) {T--;long in0 = 0, inn = 0;long n;long s0, sn;n = cinScanner.nextLong();long[] a = new long[(int) n + 2];long[] s = new long[(int) n + 1];long[] vis = new long[(int) n + 2];long[] ans = new long[(int) n + 2];for (int i = 0; i < n; i++) {a[i] = cinScanner.nextLong();s[i + 1] = a[i];s[i + 1] += s[i];}s0 = s[0];sn = s[(int) n];if (s0 > sn) {long t = s0;s0 = sn;sn = t;}Arrays.sort(s);for (int i = 0; i <= (int) n; i++)if (s[i] == s0) {in0 = i;break;}for (int i = (int) n; i >= 0; i--)if (s[i] == sn) {inn = i;break;}int l = 0;int r = (int) n;for (int i = (int) in0; i >= 0; i -= 2) {ans[l++] = s[i];vis[i] = 1;}for (int i = (int) inn; i <= n; i += 2) {ans[r--] = s[i];vis[i] = 1;}for (int i = 0; i <= n; i++)if (vis[i] == 0)ans[l++] = s[i];long res = 0;for (int i = 1; i <= n; i++)res = Math.max(Math.abs((ans[i] - ans[i - 1])), res);System.out.println(res);}}
}

• 为什么s[0]不会改变？应该只有s[n]的值不会改变
• 根本没有s[0]这种东西 有什么意义？
• 为什么重叠区隔一个取一个数可以保证正确？