题解

题面描述

小红有一个长度为 $n$ 的魔法环，环上依次有数字 $a_1, a_2, \dots, a_n$。她想通过切开并对线性序列应用交替求和，获得最佳魔法值，具体操作如下：

1. 选定一个断开位置 $k\ (1 \le k \le n)$，将环从此位置切开，得到线性序列：

2. 根据线性序列 ${b_j}$ 计算其交替求和：

小红希望在所有可能的断开位置中，使 $S$ 的值最大。请计算并输出此最大值。

思路

我们需要对长度 $n$ 的环状数组不同断开位置进行旋转，然后计算交替求和，并找到最大值。直接对每个 $k$ 都计算一次交替求和，复杂度 $O(n^2)$，在 $n\le2\times10^5$ 时无法接受。

关键在于利用递推关系在 $O(1)$ 时间内从 $S_k$ 更新到 $S_{k+1}$。设

$S_k$ = $\sum_{i=0}^{n-1}$ $(-1)^i$$a_{(k+i-1\bmod n)+1}$

即从第 $k$ 个元素开始的交替求和。可推导：

$S_{k+1}$ = -($S_k$ - $a_k$) + $(-1)^{n-1} a_k$

证明：

• $S_k$ = $a_k$ - $a_{k+1}$ + $a_{k+2}$ -......+ $(-1)^{n-1}$$a_{k-1}.$
• 去掉第一个项并整体取相反数得到前 $n-1$ 项的交替求和， ($S_k$ - $a_k$) = $a_{k+1}$ - $a_{k+2}$ +......+ $(-1)^{n-2} a_{k-1}$
• 最后再加上第 $n$ 项 $(-1)^{n-1}a_k$ 即得 $S_{k+1}$。

因此，算法流程：

1. 计算初始旋转 $S_1$ 的交替求和，时间 $O(n)$。

2. 预计算常数 $c = (-1)^{n-1}$。

3. 令 ans = S_1，然后遍历 $k=1\ldots n-1$：

   $S_{k+1} = -\bigl(S_k - a_k\bigr) + c \; a_k,$

   并更新 ans = max(ans, S_{k+1})。

4. 输出 ans。

整体复杂度 $O(n)$，空间 $O(n)$。

代码实现

C++

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

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

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

    // 1. 计算 S1 = a0 - a1 + a2 - ...
    ll S = 0;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) S += a[i];
        else S -= a[i];
    }

    // c = (-1)^(n-1)
    ll c = (n % 2 == 1 ? 1 : -1);

    ll ans = S;
    // 2. 递推计算其他旋转
    for (int k = 0; k < n - 1; k++) {
        // 更新到 S_{k+2}
        S = -(S - a[k]) + c * a[k];
        ans = max(ans, S);
    }

    cout << ans;
    return 0;
}

Python

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:]))

    # 1. 计算 S1
    S = sum(a[i] if i % 2 == 0 else -a[i] for i in range(n))

    # c = (-1)^(n-1)
    c = 1 if n % 2 == 1 else -1

    ans = S
    # 2. 递推
    for k in range(n-1):
        S = -(S - a[k]) + c * a[k]
        ans = max(ans, S)

    print(ans)

if __name__ == '__main__':
    main()

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        // 1. 计算 S1
        long S = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) S += a[i];
            else S -= a[i];
        }

        // c = (-1)^(n-1)
        long c = (n % 2 == 1) ? 1 : -1;

        long ans = S;
        // 2. 递推其他旋转
        for (int k = 0; k < n - 1; k++) {
            S = -(S - a[k]) + c * a[k];
            ans = Math.max(ans, S);
        }

        System.out.println(ans);
    }
}

题目内容

小红有一个长度为 $n$ 的魔法环，环上依次有数字 $a_1,a_2,…,a_n$ 。 她想通过切开并对线性序列应用交替求和，获得最佳魔法值具体步骤：

1.选定一个断开位置 $k (1≤k≤n)$ ，循环从此位置切开，得到线性序列

$b_1=a_k,b_2=a_{k+1},…, b_ {n-k+1}=a_n$,$b_{n-k+1}=a_n$,$b_{n-k+2}=a_1$$,...,$$b_n=a_{k-1}$。

2.根据线性序列{$b_j$}计算其交替求和：$S = b_1 - b_2 + b_3 - b_4 + … + (-1)^{n-1}b_n$ 。

小红希望在所有可能的断开位置中，$S$ 的值最大。请你计算并输出此最大值。

输入描述

第一行输入一个整数 $n (1≤n≤2×10^5)$，表示魔法环上的数字个数。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n (0≤a_i< n)$ ，代表环上各位置的初始数字。

输出描述

输出一个整数，表示小红在所有断开位置的交替求和中能获得的最大魔法值。

样例1

输入

4
1 2 3 2

输出

0

说明

对于任意断开位置，线性序列的交替求和均为 $0$ 。

样例2

输入

6
1 2 3 2 5 0

输出

5

说明

当断开位置 $k = 1$ 时，序列 $[1,2,3,2,5,0]$ 的交替求和为 $1-2+3-2+5-0=5$ ，是所有位置中的最大值。