题解 P5146 【最大差值】
rui_er
2019-07-12 13:21:11
# C++语言题解
~~P党再见~~
看见标签：DP，想~~DP我不会~~这样发不了题解，于是有以下思路
思路：最大差值……差值！（划重点）差值怎么办呢？当然是用差分了！
懂了的退出自己想想。
差分，具体怎么办呢？最大差值，即找出差分数组的最大子段和。特别地，这里差分数组第一个位置要置成非正数（因为不能取第一个数前面隐藏的0），否则样例会过不了。
## 样例解释
|类型|0|1|2|3|4|5|6|7|8|9|
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
|原数组|1|3|4|6|7|9|10|1|2|9|
|差分|-1000000|2|1|2|1|2|1|-9|1|7|
|最大子段和||*|*|*|*|*|*||||
最大子段和为```d[1]+d[2]+d[3]+d[4]+d[5]+d[6]```，换回原数组即为```a[1]-a[0]+a[2]-a[1]+a[3]-a[2]+a[4]-a[3]+a[5]-a[4]+a[6]-a[5]```，即```a[6]-a[0]```，为最大差值。
## 代码：
```cpp
#include <iostream>
#include <limits.h>
using namespace std;
int n, a[1000001], d[1000001], f[1000001];
int maxsum(void)
{
f[0] = d[0];
for(int i=1;i<n;i++) f[i] = max(f[i-1] + d[i], d[i]);
int m = INT_MIN;
for(int i=0;i<n;i++) m = max(m, f[i]);
return m;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
d[i] = i ? (a[i] - a[i-1]) : -1000000;//差分
}
// for(int i=0;i<n;i++) cout<<d[i]<<" ";
// cout<<endl;
cout<<maxsum()<<endl;
return 0;
}
```