题解

题面描述

给定一个长度为$n$的整数数组$a$（元素可为正、负或零），你拥有一次“取反”操作的能力：可以任选一个连续子数组，将其中每个元素都变为相反数。该操作最多执行一次（也可不执行）。操作之后，你再任选一个非空的连续子数组，取其元素之和。问：通过恰当地选择取反区间（或不取反）以及最后取和的区间，能够获得的最大子数组和是多少？

思路

我们需要在“取反”与“取和”两个自由度下同时优化。令最终选取的求和区间为 $[L,R]$，取反区间为 $[l,r]$。如果取反区间与求和区间有重叠，就会对被重叠部分产生符号翻转；如果无重叠，取反操作对求和区间无影响。枚举两者在 $O(n^2)$ 当然不可行。

可用动态规划，将状态按「操作进度」划分为三种，以 $i$ 为结尾的最优子数组和分别是：

• $dp_0[i]$: 前 $i$ 个元素内，不使用取反操作，以 $i$ 结尾的最大子数组和。
• $dp_1[i]$: 前 $i$ 个元素内，取反操作正在进行中（区间已开始且尚未结束），以$i$结尾的最大子数组和。 *$dp_2[i]$: 前 $i$ 个元素内，取反操作已完成，以 $i$ 结尾的最大子数组和。

三个状态的转移如下：

• 对于$dp_0$，即普通的「不含取反」的最大子数组和。
• 对于$dp_1$，如果仍在取反阶段，则对当前$a_i$ 要取反，所以加上$(-a_i)$；可以从上一个状态继续取反（$dp_1[i-1]-a_i$），也可以刚从未取反状态开始取反（$dp_0[i-1]-a_i$）。
• 对于$dp_2$，取反结束后，恢复正常累加：可以继续在已完成取反后的子数组内累加（$dp_2[i-1]+a_i$），也可以刚结束取反、转入正常阶段（$dp_1[i-1]+a_i$）。

初始时（$i=1$）：

最终答案即为

该算法只需一次遍历，时间复杂度$O(n)$，空间可优化至$O(1)$。

C++

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

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

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

    // 初始化 dp0, dp1, dp2
    long long dp0 = a[1];     // 未取反
    long long dp1 = -a[1];    // 正在取反
    long long dp2 = a[1];     // 已取反
    long long ans = max({dp0, dp1, dp2});

    for (int i = 2; i <= n; i++) {
        long long x = a[i];
        long long prev0 = dp0, prev1 = dp1, prev2 = dp2;

        // 状态转移
        dp0 = max(prev0 + x, x);
        dp1 = max(prev1 - x, prev0 - x);
        dp2 = max(prev2 + x, prev1 + x);

        // 更新答案
        ans = max({ans, dp0, dp1, dp2});
    }

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

Python

def max_subarray_with_one_flip(a):
    # a: 1-based 索引或直接切片也行
    dp0 = a[0]     # 未取反
    dp1 = -a[0]    # 正在取反
    dp2 = a[0]     # 已取反
    ans = max(dp0, dp1, dp2)

    for x in a[1:]:
        prev0, prev1, prev2 = dp0, dp1, dp2

        # 三个状态的转移
        dp0 = max(prev0 + x, x)
        dp1 = max(prev1 - x, prev0 - x)
        dp2 = max(prev2 + x, prev1 + x)

        ans = max(ans, dp0, dp1, dp2)

    return ans

if __name__ == "__main__":
    import sys
    data = list(map(int, sys.stdin.read().split()))
    n, arr = data[0], data[1:]
    print(max_subarray_with_one_flip(arr))

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().trim());
        String[] parts = br.readLine().split("\\s+");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = Long.parseLong(parts[i]);
        }

        // 三个状态的初始化
        long dp0 = a[0];    // 未取反
        long dp1 = -a[0];   // 正在取反
        long dp2 = a[0];    // 已取反
        long ans = Math.max(dp0, Math.max(dp1, dp2));

        for (int i = 1; i < n; i++) {
            long x = a[i];
            long prev0 = dp0, prev1 = dp1, prev2 = dp2;

            // 状态转移
            dp0 = Math.max(prev0 + x, x);
            dp1 = Math.max(prev1 - x, prev0 - x);
            dp2 = Math.max(prev2 + x, prev1 + x);

            // 更新最大值
            ans = Math.max(ans, Math.max(dp0, Math.max(dp1, dp2)));
        }

        System.out.println(ans);
    }
}

题目内容

你有一个包含整数的数组$a$，数组中的每个元素可以是正数、负数或零。

现在，你拥有一种特殊的能力:

你可以选择数组中的任意一段连续的子数组，并将这段子数组内的每个数字都变换成其相反数。这个操作可以执行$0$次或$1$次。

你的任务是，利用这个特殊能力，找出在执行操作后能够达到的最大和的连续子数组。这里所指的“最大和"是指经过可能的变换操作后，任意连续子数组元素之和的最大值。需要注意的是，最终选择的子数组至少应包含一个元素。注意:取反的子数组跟最终求和的子数组并不需要相同

输入描述

第一行包含一个整数$n(2≤n≤10^5)$，表示数组中数字的个数。

第二行包含$n$个整数，依次为$a_1,a_2,..,a_n(-10^4≤a≤10^4)$

输出描述

输出一个整数，表示在执行操作后能够达到的最大和的连续子数组之和。

样例1

输入

6
3 1 -6 2 -5 3

输出

16

说明

首先选择$[-6,2,-5]$进行变换，原数组变为$[3,1,6,-2,5,3]$，此时选择整个数组序列，可得最大总和为$16$。

样例2

输入

7
-1 -1 8 -9 7 -1 -1

输出

24

说明

首先选择子数组$[-9]$进行变换，原数组变为$[-1,-1,8,9,7,-1,-1]$，此时选择$[8,9,7]$子数组，可得最大总和为$24$。

样例3

输入

5
1 3 4 2 5

输出

15

说明

首先不进行任何变换，然后此时选择整个数组序列，可得最大总和为$15$