小红书2023秋招提前批

2024-07-09 18:29| 来源: 网络整理| 查看: 265

https://oj.algomooc.com/problem.php?id=5900 小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为\(x\)。小红想知道，最终的连续子数组最大和最大是多少？

输入第一行输入一个正整数\(t\)，代表询问次数。对于每次询问，输入两行：第一行输入两个整数\(n\)和\(x\)。代表数组的大小，以及小红可以修改成的元素。第二行输入n个正整数\(a_i\)，代表小红每次询问拿到的数组。 \(1 ≤ t ≤ 100000\) \(1 ≤ n ≤ 200000\) \(-10^9 ≤ x, a_i ≤ 10^9\) 每组所有询问的n的和不超过200000。

输出输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。

样例输入复制 3 5 10 5 -1 -5 -3 2 2 -3 -5 -2 6 10 4 -2 -11 -1 4 -1 样例输出复制 15 -2 15 提示第一组询问，修改第二个数。第二组询问，不进行任何修改。第三组询问，修改第三个数。

首先这个题如果不能修改的话，我们知道是一个dp，dp[i]为前i个最大值，状态转移方程为 dp[i]=max(dp[i-1]+a[i],a[i]) 然后这个题他最多可以修改一个数字，这里我们需要考虑他什么时候修改，那么这就有两个状态了，就是 dp[i][1]表示前i个有修改的最大值，dp[i][0]表示没有修改的最大值。然后状态转移方程就是：这个就是没修改：

dp[i][0]=max(dp[i-1][0]+a[i],a[i]);

然后就是修改的，我们需要考虑他是第i个修改的还是前i-1个修改的：

dp[i][1]=max(dp[i-1][0]+x,x);//修改第i个 dp[i][1]=max(dp[i-1][1]+a[i],max(dp[i][1],a[i]));

code

#include #include #include #include using namespace std; const int maxn=1e6+100; int dp[maxn][2]; int a[maxn]; int main(){ int t; cin>>t; while(t--){ int n,x; cin>>n>>x; memset(dp,-0x3f3f3f3f,sizeof(dp)); for(int i=1;i>a[i]; } for(int i=1;i

【本文地址】

公司简介

联系我们