首页 > 试题广场 >

小苯的最大和

[编程题]小苯的最大和

热度指数：633 时间限制：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$ 的最大总和可以达到多少，请你帮他算一算吧。

输入描述:

本题有多组测试数据。
输入的第一行包含一个正整数 ，表示数据组数。
接下来包含  组数据，每组数据的格式如下：
第一行一个正整数 ，表示数组  的初始长度。
第二行  个整数 ，表示数组 。
（保证所有测试数据中， 的总和不超过 。）

输出描述:

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

示例1

输入

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

输出

20
15

说明

对于第一组测试数据：
我们首先使用第一种删除 ，此时 。
再使用第二种操作删除 ，此时 。
接在我们再使用第一种操作删除 ，此时 。
此时数组  的总和等于  最大。

可以证明不存在更优的答案。

算法知识视频讲解

hdhzh666

发表于 2026-01-29 17:20:34

定义dp[i]为以i结尾数组的最大总和，则需要求dp[n-1]可以从边界开始推当只有一个数时dp[0]=a[0]有两个数时可以选择删2 或者不删即dp[1]=max(0,a[0]+a[1])有三个数时可以选择删3 对应0 ，删2：删a[1]和a[2] 剩下a[0](就是dp[0]),不删就展开全文

周康禧

发表于 2025-12-10 23:35:04

#include <bits/stdc++.h> using namespace std; using ll = long long int; using ld = long double; using PII=pair<ll,ll>; using PIII=pair< 展开全文

丘馗

发表于 2026-01-27 16:08:10

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int T;cin>>T; for(int i= 展开全文

王同学8

发表于 2025-12-17 15:03:56

def test(n:int,a:list): if n==1: return a[0] dp = [0 for _ in range(n+1)] dp[1]=a[0] for i in range(2,n+1): dp[i]=max( 展开全文

蟑螂是只爬虫

发表于 2025-12-07 16:26:23

定义: dp[i]为以下标i为结尾的最大子序列和状态转移方程: 解释: 如果不删除,dp[i]可以由dp[i-1]转移过来; 如果删除,由裴蜀定理 ,一定可以从dp[i-3]及其之前的任意位置转移过来,我们使用一个变量在遍历过程中记录dp[i-3]的前缀最大值即可; 当然也可以从当前节展开全文

哈基图

发表于 2026-02-01 16:55:30

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll T; cin>>T; while(T--){ ll n; 展开全文

问题信息

难度：

1条回答 3收藏 30浏览

小苯的最大和

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题