思路： d p dp dp。
考虑：分数组长度的奇偶性进行 d p dp dp。
令 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示前 i i i个数答案为偶数长度的最大值， d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示前 i i i个数答案为奇数长度的最大值。
显然有状态转移方程：
d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] − a [ i ] ) dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i]) dp[i][0]=max(dp[i−1][0],dp[i−1][1]−a[i])
d p [ i ] [ 1 ] = m a x ( d p [ i − 1 ] [ 1 ] , d p [ i − 1 ] [ 0 ] + a [ i ] ) dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]) dp[i][1]=max(dp[i−1][1],dp[i−1][0]+a[i])
答案即为： m a x ( d p [ n ] [ 0 ] , d p [ n ] [ 1 ] ) max(dp[n][0],dp[n][1]) max(dp[n][0],dp[n][1])
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int t,n,q,a[N]; ll dp[N][2]; int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); dp[0][0]=0,dp[0][1]=-inf; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); dp[i][0]=max(dp[i-1][0],dp[i-1][1]-a[i]); dp[i][1]=max(dp[i-1][1],dp[i-1][0]+a[i]); } printf("%lld\n",max(dp[n][0],dp[n][1])); } return 0; }