https://codeforces.com/contest/1420/problem/C1
题意：有一个a序列，要你找一个子序列，结果为奇数位减去偶数位的和。求最大和。
对于c1来说，有两种方法。采用贪心，c2的维护就讨论交换的时候是具体什么情况；采用dp，c2的维护就可以使用线段树来维护这个dp。
先上dp的转移叭..我当时是用贪心过的。
定义dp[i][0]为前i个数选择了偶数个数的最大和；dp[i][1]为选择了奇数个数的最大和。
dp[i][1]=max(dp[i?1][1],dp[i?1][0]+a[i]);
dp[i][0]=max(dp[i?1][0],dp[i?1][1]?a[i]);
考虑贪心：可以比较直观的发现，数的个数肯定是奇数的时候比偶数更优，因为能多加嘛。所以贪心去考虑就是说我先找到一个能尽量的，在后面找一个能最小的，再之后找一个尽量大的，如此往复能达到最优的结果。边界是就取一个数。
这么贪心的话实际上就是在序列中找波峰波谷。那么是否是最优的呢？设后面获得的值为x,假如不取第一个波峰，取波峰旁边的数肯定不如波峰+x更大，因为波峰大于旁边的数。波谷也是一样的道理。
代码上注意：处理a[n+1]的时候要清空，因为多组输入这时候可能会导致用到了上一组的a[n+1]。(天知道我因为这个思考了好久的人生)
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=3e5+100;
typedef long long LL;
LL a[maxn];
int main(void)
{cin.tie(0);std::ios::sync_with_stdio(false);LL t;cin>>t;while(t--){LL n,q;cin>>n>>q;LL mx=-0x3f3f3f3f;for(LL i=0;i<=n+10;i++) a[i]=0;for(LL i=1;i<=n;i++) cin>>a[i],mx=max(a[i],mx);LL sum=0;LL flag=1;for(LL i=1;i<=n;i++){if(a[i]>a[i-1]&&a[i]>a[i+1]&&flag==1) sum+=a[i],flag=-1;//cout<<a[i]<<" ";else if(flag==-1&&a[i]<a[i-1]&&a[i]<a[i+1]) sum-=a[i],flag=1;//cout<<a[i]<<" ";}cout<<max(sum,mx)<<endl;}
return 0;
}