(这貌似是个日本的oj？名字叫aizu有点奇怪呢hhhh)
这道题的思路是首先将相减转化为相加。我们可以在原数组的基础上再构造一个新的数组sub[],sub[]中存放的是R[i+1]-R[i]，因此，有以下式子成立： (R[i+1]-R[i]) + (R[i+2]-R[i+1]) + ··· + (R[j-1]-R[j-2]) + (R[j] - R[j-1]) = sub[i+1] + sub[i+2] + ··· + sub[j-1] + sub[j] = R[j] - R[i] 这么一来，求差的最大值就转化为了求sub[]的连续子序列和的最大值，而这只需要用dp求即可。状态转移方程为dp[j] = max(dp[j-1] + sub[j],sub[j])。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=200000+5;
ll R[maxn];
ll sub[maxn];
ll dp[maxn];
int main()
{
int n;
memset(R,0,sizeof(R));
memset(sub,0,sizeof(sub));
memset(dp,0,sizeof(dp));
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&R[i]);
for(int i=1;i<=n-1;i++)
sub[i]=R[i+1]-R[i];
dp[1]=sub[1];
ll ans=INT_MIN;
for(int i=2;i<=n-1;i++)
dp[i]=max(dp[i-1]+sub[i],sub[i]);
for(int i=1;i<=n-1;i++)
if(dp[i]>ans)
ans=dp[i];
printf("%lld\n",ans);
return 0;
}