首页 > 试题广场 >

小苯的最大和

[编程题]小苯的最大和
  • 热度指数：634 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小苯有一个长度为 n 的数组 a，但 a 中可能存在一些负数会使得 a 的总和不够大。
现在小苯希望 a 的总和（即：\{a_1+a_2+...+a_n\}）尽可能大，为此他可以做如下操作任意次（两种都任意次）：

\hspace{15pt}\bullet 选择两个相邻的数字 a_i 和 a_{i+1}\ (1 \leq i < |a|)，将其删除，其余数字顺次拼接起来。（换句话说操作后 a 数组变为：\{a_1,a_2,...,a_{i-1},a_{i+2},...,a_n \}。）

\hspace{15pt}\bullet 选择三个连续的数字 a_i,a_{i+1} 和 a_{i+2}\ (1 \leq i < |a|-1)，将其删除，其余数字拼接起来。（换句话说操作后 a 数组变为：\{a_1,a_2,...,a_{i-1},a_{i+3},...,a_n \}。）

以上操作小苯均可执行任意次，他想知道数组 a 的最大总和可以达到多少，请你帮他算一算吧。

输入描述:
本题有多组测试数据。
输入的第一行包含一个正整数 T\ (1 \leq T \leq 100)，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行一个正整数 n\ (1 \leq n \leq 2 \times 10^5)，表示数组 a 的初始长度。
第二行 n 个整数 a_i\ (-10^9 \leq a_i \leq 10^9)，表示数组 a。
（保证所有测试数据中，n 的总和不超过 2 \times 10^5。）


输出描述:
对于每组测试数据：
在单独的一行输出一个整数，表示数组 a 的最大总和。
示例1

输入

2
12
1 3 -2 -1 -4 -1 -2 5 -4 15 -10 9
5
1 2 3 4 5

输出

20
15

说明

对于第一组测试数据：
我们首先使用第一种删除 i=3,i=4，此时 a=\{1,3,-4,-1,-2,5,-4,15,-10,9\}。
再使用第二种操作删除 i=2,i=3,i=4，此时 a=\{1,3,5,-4,15,-10,9\}。
接在我们再使用第一种操作删除 i=6,i=7，此时 a=\{1,3,5,-4,15\}。
此时数组 a 的总和等于 20 最大。

可以证明不存在更优的答案。
算法知识视频讲解
添加回答
精致的熊熊在努力存钱头像 精致的熊熊在努力存钱
def func(n:int,li:list):
    dp = [0] * n
    for i in range(n):
        if i == 0:
            dp[i] = li[i]
        elif i == 1:
            dp[i] = max(0,li[0]+li[1])
        elif i == 2:
            dp[i] = max(0,dp[0],dp[1]+li[i])
        else:
            dp[i] = max(dp[i-3],dp[i-2],dp[i-1]+li[i])
    return dp[-1]

T = int(input())
for _ in range(T):
    print(func(int(input()),list(map(int,input().split()))))
发表于 2026-02-11 21:12:34 回复(0)
提交观点

问题信息

难度：
1条回答 32浏览

热门推荐

相关试题

小苯的最大和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号