题面描述：

多多正在玩一个一维数轴上的传送门游戏。游戏开始时，他位于 $x = 0$ 位置，一共有 $n$ 个传送门依次可用（顺序为 $1$ 到 $n$，不能更改使用顺序）。第 $i$ 个传送门有一个传送值 $a_i$，当多多使用该传送门时，会将他的当前位置 $x$ 改变为 $x + a_i$。传送门是一次性的，用过就不能再用。

此外，多多拥有一次“反转”技能，可以在任意时刻将当前位置从 $x$ 变为 $-x$，该技能至多只能使用一次（也可选择不用）。当多多先后使用完 $1$ 到 $n$ 号传送门后，我们想知道在整个传送/反转的过程中，多多与初始位置（$0$ 点）之间的最大距离是多少（即最大值 $\max |x|$）。

思路与详细解析

1. 前缀和的构造

   为了方便分析在依次使用每个传送门后的当前位置，可定义前缀和数组 $s$，其中：

$s[0] = 0,s[i] = a_1 + a_2 +...+ a_i (i>=1).$

• 当多多使用完前 $i$ 个传送门后，所处位置即为 $s[i]$。
• 因此在尚未使用反转技能时，多多可能出现的位置就是 $s[0], s[1], \dots, s[n]$。

3. 不使用反转技能时的最大距离

   首先可以计算在不使用反转技能的情况下，多多所能达到的最大距离：

   $$\max_{\,0 \le i \le n} \bigl|\,s[i]\,\bigr|.$$

   这一步直接遍历所有前缀和 $s[i]$ 的绝对值，取最大值即可。

4. 为后半段准备：后缀最大值、后缀最小值

   当选择在某个时刻（可以是在使用完某个传送门后）执行“反转”时，后续位置会受到影响：

   • 如果我们在第 $i$ 步传送结束后（此时位置为 $s[i]$）执行反转操作，那么后续任何时刻（例如使用完第 $j$ 个门，且 $j \ge i$）的位置可写为：$$s[j] \;-\; 2\,s[i].$$ 这相当于先有原本的 $s[j]$，再把之前累计的 $s[i]$ “取反”，使后续状态整体平移 $-\,2\,s[i]$。
   • 为了快速获知在 $j \ge i$ 范围内的 $\max(s[j])$ 与 $\min(s[j])$，可以从后往前预处理两类后缀数组：
     • $Mplus[i] =max{s[i],s[i+1]......s[n]}$
     • $Mminus[i] =min{s[i],s[i+1]......s[n]}$

5. 枚举反转时机，计算最大距离

   • 在所有可能的反转点 $i$（从 $0$ 到 $n$ 都可反转，包括在一开始或最后的特殊情形），假设在第 $i$ 步传送完毕后位置为 $s[i]$，执行一次反转，则后续使用第 $i+1$ 到第 $n$ 个传送门时，位置将由原先的 $s[j]$（$j \ge i$）变为 $s[j] - 2,s[i]$。
   • 对此后半段位置的最大绝对值可通过后缀数组立刻得到： $max{|Mplus[i]- 2s[i]|,|Mminus[i]-2s[i]|}$
   • 枚举 $i$ 并取以上值的最大值，就是在使用一次反转技能后可能达到的最大绝对距离。
   • 最后，与“不使用反转技能时的最大值”取最大，即为最终答案。

cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * 问题：在使用n个传送门的过程中，每个门依次把位置从 x 转到 x + a[i]。
 *       我们可以在任意时刻使用一次“反转”技能 ( x -> -x )，求能够达到的离 0 最远的距离 (最大|x|)。
 * 思路：前缀和 + 后缀最大/最小值。
 */

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    // 1) 计算前缀和 s[0..n]，其中 s[0] = 0, s[i] = a1 + ... + a_i
    vector<long long> s(n+1, 0LL);
    for(int i=1; i<=n; i++){
        s[i] = s[i-1] + a[i-1];
    }

    // 2) 先计算不使用反转技能时，在整个过程中出现的 |s[i]| 的最大值
    long long ans = 0;
    for(int i=0; i<=n; i++){
        ans = max(ans, llabs(s[i]));
    }

    // 3) 计算后缀最大值 Mplus[i] = max(s[i], s[i+1], ..., s[n])
    //           后缀最小值 Mminus[i] = min(s[i], s[i+1], ..., s[n])
    vector<long long> Mplus(n+1), Mminus(n+1);
    Mplus[n] = s[n];
    Mminus[n] = s[n];
    for(int i=n-1; i>=0; i--){
        Mplus[i] = max(Mplus[i+1], s[i]);
        Mminus[i] = min(Mminus[i+1], s[i]);
    }

    // 4) 枚举反转点 i (含 i=0, i=n)，然后计算后半段可能的最大|位置|
    //    若在第i步(用完第i个门)反转，则后续位置为 s[j] - 2*s[i] (j>=i)
    //    我们只需看 Mplus[i], Mminus[i] 与 2*s[i] 的差值谁绝对值更大
    for(int i=0; i<=n; i++){
        long long val1 = llabs(Mplus[i] - 2LL*s[i]);
        long long val2 = llabs(Mminus[i] - 2LL*s[i]);
        long long cand = max(val1, val2);
        ans = max(ans, cand);
    }

    cout << ans << "\n";
    return 0;
}

python

import sys

# 一次性读取输入数据
data = sys.stdin.read().strip().split()
n = int(data[0])
a = list(map(int, data[1:]))

# 1) 计算前缀和 s[0..n]，s[0] = 0, s[i] = a1 + ... + a_i
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i - 1]

# 2) 不使用反转技能时，在过程中出现的 |s[i]| 的最大值
ans = 0
for i in range(n + 1):
    ans = max(ans, abs(s[i]))

# 3) 计算后缀最大值 Mplus[i] = max(s[i..n])
#           后缀最小值 Mminus[i] = min(s[i..n])
Mplus = [0] * (n + 1)
Mminus = [0] * (n + 1)
Mplus[n] = s[n]
Mminus[n] = s[n]
for i in range(n - 1, -1, -1):
    Mplus[i] = max(Mplus[i + 1], s[i])
    Mminus[i] = min(Mminus[i + 1], s[i])

# 4) 枚举反转点 i (包含 i=0 和 i=n)
#    在第 i 步(用完第 i 个门)反转后，后续位置变为 s[j] - 2*s[i] (j >= i)
#    比较 Mplus[i] - 2*s[i] 和 Mminus[i] - 2*s[i] 的绝对值
for i in range(n + 1):
    val1 = abs(Mplus[i] - 2 * s[i])
    val2 = abs(Mminus[i] - 2 * s[i])
    ans = max(ans, val1, val2)

print(ans)

java

import java.util.*;
import java.io.*;

public class Main {
    /*
     * 问题：同上
     * 思路：同上
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] a = new long[n];
        for(int i=0; i<n; i++){
            a[i] = in.nextLong();
        }
        in.close();

        // 1) 前缀和
        long[] s = new long[n+1];
        for(int i=1; i<=n; i++){
            s[i] = s[i-1] + a[i-1];
        }

        // 2) 不反转时的最大|s[i]|
        long ans = 0;
        for(int i=0; i<=n; i++){
            ans = Math.max(ans, Math.abs(s[i]));
        }

        // 3) 后缀最大最小
        long[] Mplus = new long[n+1];
        long[] Mminus = new long[n+1];
        Mplus[n] = s[n];
        Mminus[n] = s[n];
        for(int i=n-1; i>=0; i--){
            Mplus[i] = Math.max(Mplus[i+1], s[i]);
            Mminus[i] = Math.min(Mminus[i+1], s[i]);
        }

        // 4) 枚举反转点并更新答案
        for(int i=0; i<=n; i++){
            long val1 = Math.abs(Mplus[i] - 2*s[i]);
            long val2 = Math.abs(Mminus[i] - 2*s[i]);
            ans = Math.max(ans, Math.max(val1, val2));
        }

        System.out.println(ans);
    }
}

题目内容

多多在玩一个传送门游戏。

游戏开始时多多在一维数轴的$x=0$处。他有$n$个传送门，每个传送门都有一个传送值$a_i$，他能

使用该传送门从$x=t$位置传送到$x=t+a_i$，传送门是消耗品，只能使用一次。同时他还有一 个“反转”技能，使用该技能可以立即从位置$x=t$“反转”到$x=-t$.

多多必须从$1$到$n$使用这些传送门，可以在任何时候使用“反转”技能(最多用一次，也可以不 用)，问用完所有传送门后，多多到初始位置$x=0$最远的距离为多少?

输入描述

第一行为一个正整数$n(1≤n≤10^5)$，

第二行为$n$个整数 $a_1,a_2,….,a_n (-10^9≤a_i≤10^9)$。

输出描述

输出在传送的过程中，多多到初始位置距离的最大值。

补充说明

对于 $60$ 的数据,$1≤n≤1000$;

对于100% 的数据，$1≤n≤10^5,-10^9≤a_i≤10^9$.

样例1

输入

4
1 1 -1 1

输出

3

说明

最初多多在位置$x=0$处;

他先依次使用第$2$个传送门，到达位置$x=0+a_1+a_2=0+1+1=2$，与初始位置距离为$2$

然后他使用技能“反转”，到达位置$x=-2$，与初始位置距离为$2$;

再使用第$3$个传送门，到达位置$x=-2+a_3=-2-1=-3$，与初始距离为$3$;

最后使用第$4$个传送门，到达位置$x=-3+a_4=-3+1=-2$,与初始位置距离为$2$

在传送的过程中，与初始位置距离最大为3.

样例2

输入

5
1 -4 10 -30 2

输出

37

说明

多多在使用过前$3$个传送门后到达$x=7$;

此时使用一次“反转”，到达$x=-7$;

再使用第$4$个传送门到达$x=-37$，此时与初始位置距离最远，为$37$。