大一新生求助一道动态规划思维题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
long a[100001];
LL y,x;
long read() {
long f = 1, k = 0;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();}
while(c >= '0' && c <= '9'){
k=k * 10 + c - '0';
c = getchar(); }
return f * k;}
long max1=0;
int t1=1;
void main2() {
cin>>y;
for(int i=0;i<y;i++)
a[i]=read();
while(t1)
{
t1=0;
for(int i=1;i<(y-1);i++)
{
if(a[i]<(a[i-1]+a[i+1]-a[i]))
{
t1++;
a[i]=a[i+1]+a[i-1]-a[i];
}
}
}
for(int i=0;i<y;i++)
max1=max(max1,a[i]);
cout<<max1<<"\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> x;
//x = 1;
while (x--) main2();
return 0;
}

这题和dp没什么关系，不知道你有没有学过差分数组
执行一次操作之后，实际上是在差分数组上交换两个相邻的数字
我们可以把正的都交换到前面，负的都交换到后面，这样就能得到最大值了
线性时间就能做完