考虑枚举每个子串开头的位置,然后答案转化成询问这个位置之后 哪个位置的前缀和 - 这位置的前缀和 最大(当然是已经把绝对值和正负的情况处理好了,可以发现按奇偶,这个序列只有两种情况),只需要预处理这两个序列的前缀和,以及这两个前缀和序列的后缀max即可。

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
int Abs(int x){
return x<0 ? (-x) : x;
}
int n;
int a[100010],b[100010];
ll d[100010],c[100010],e[100010],f[100010],ans;
int main(){
// freopen("c.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<n;++i){
b[i]=Abs(a[i+1]-a[i]);
}
int op=1;
for(int i=1;i<n;++i){
c[i]=c[i-1]+(ll)(b[i]*op);
op=-op;
}
op=-1;
for(int i=1;i<n;++i){
d[i]=d[i-1]+(ll)(b[i]*op);
op=-op;
}
ll maxn=-1e18;
for(int i=n-1;i>=1;--i){
maxn=max(maxn,c[i]);
e[i]=maxn;
}
maxn=-1e18;
for(int i=n-1;i>=1;--i){
maxn=max(maxn,d[i]);
f[i]=maxn;
}
for(int i=1;i<n;i+=2){
ans=max(ans,e[i]-c[i-1]);
}
for(int i=2;i<n;i+=2){
ans=max(ans,f[i]-d[i-1]);
}
cout<<ans<<endl;
return 0;
}

最新文章

  1. Android中访问sdcard路径的几种方式
  2. oracle连接问题【转载】
  3. 【maven】之配置开发,测试,正式环境pom.xml文件
  4. web服务器长连接
  5. iOS开发之UITableView使用总结
  6. python 加密解密(base64, AES)
  7. C#中的ICollection接口
  8. struts2关于package 的 namespace
  9. java中文乱码解决之道(六)—–javaWeb中的编码解码
  10. [c#]asp.net开发微信公众平台(5)微信图文消息
  11. 如何在在网页上显示pdf文档
  12. [Usaco2007 Dec]Building Roads 修建道路[最小生成树]
  13. androidstudio连接SCM Manager上的Git库
  14. Android 自定义 ViewPager 打造千变万化的图片切换效果
  15. [Swift]LeetCode794. 有效的井字游戏 | Valid Tic-Tac-Toe State
  16. Js修改input值后怎么同步修改绑定的v-model值
  17. fiddler中断request,修改参数问题
  18. git撤销中间的某次提交
  19. 【Java并发核心四】Executor 与 ThreadPoolExecutor
  20. 源码分析篇 - Android绘制流程(二)measure、layout、draw流程

热门文章

  1. java 深度拷贝 复制 深度复制
  2. Winform MD5
  3. jQuery实现用户头像裁剪插件cropbox.js
  4. Vuex 基本概念
  5. 转载: GIt远程操作详解
  6. [LabVIEW架构]ActorFramework(二)
  7. jdk1.8在linux环境下的安装
  8. Makefile系列之三 : 变量
  9. Webstorm和Eclipse常用快捷键
  10. Linux Python apache的cgi配置