题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

执行如下操作，直到$a$中只剩下$1$个数：

• 删除$a[i]$，如果$a[i]$左右两边都有数字，则把$a[i-1]$和$a[i+1]$合并成一个数。

输出最后剩下的那个数的最大值。

输入样例

3
6
-3 1 4 -1 5 -9
5
998244353 998244353 998244353 998244353 998244353
1
-2718

输出样例

9
2994733059
-2718

算法

动态规划

这个题乍一看感觉很贪心或者并查集，但是最后发现DP可以做。由于每次删除一个数之后，合并的是两个下标奇偶性相同的数，所以本质上这个题目就是在求一个子序列，子序列中每个数在原数组中的下标之差都是偶数的情况下，子序列的最大和。

状态定义

$dp[i]$表示保留$a[i]$，且以$a[i]$结尾的序列中的最大和，在这个定义下$max_{i \in [1,n]}dp[i]$就是答案。

状态转移

当遍历到$a[i]$时，它可以接在一个子序列后面，这个子序列的结尾是一个下标$j \lt i$且奇偶性和$i$相同的数，所以状态转移方程为$dp[i]=max(a[i],dp[j]+a[i])$，其中$j \lt i$且$j$与$i$奇偶性相同。为了$O(1)$进行状态转移，我们就可以维护一个长度为$2$的数组$ma$，$ma[0]$表示所有$j \lt i$的偶数下标$dp[j]$的最大值，$ma[1]$表示所有$j \lt i$的偶数下标$dp[j]$的最大值，可以一边DP一边维护。

复杂度分析

时间复杂度

状态数量为$O(n)$，单次转移为$O(1)$，因此时间复杂度为$O(n)$。

空间复杂度

除去输入的数组$a$，空间消耗的瓶颈就是DP数组。即动态规划的状态数量，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
const LL INF = 1e15;
int T, n, a[N];
LL dp[N], ma[2];

void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    if(n == 1) {
        printf("%d\n", a[1]);
        return;
    }
    LL ans = a[1];
    dp[1] = a[1];
    ma[0] = ma[1] = -INF;
    ma[1] = max(ma[1], 1LL*a[1]);
    for(int i = 2; i <= n; i++) {
        dp[i] = max(1LL*a[i], ma[i&1] + a[i]);
        ma[i&1] = max(ma[i&1], dp[i]);
        ans = max(ans, dp[i]);
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}