题目描述
薯片和他的朋友薯条来到了商店，商店有n个糖果，标号依次为1,2,3....n1,2,3....n，对应的价值为W_1,W_2,W_3,...,W_nW1,W2,W3,...,Wn。现在薯片先拿走一个标号为aa的糖果，标号小于a的糖果就被商家收回去了，然后薯条只能在剩下的糖果中选一个标号为b的糖果，请问W_a-W_bWa−Wb的最大值是多少？
输入描述
多组数据输入，每一组数据第一行输入一个数字 n(2≤nle 100000)n(2≤n≤100000),接下来nn行，每行输入一个w_iwi表示第ii个糖果的价值(0
输出描述
每组数据输出W_a-W_bWa−Wb的最大值
样例输入
3
3 2 1
6
1 1 1 1 1 1
样例输出
2
0
#include
#include
using namespace std;
int a[100005],m[100005],f[100005];//a记录题给数据，m记录从最后开始到当前位置的最小值，f记录针对当前位置讨论的最小Wa-Wb
int main()
{
int n,i,ans;
while(cin>>n)
{
for(i=1;i<=n;i++)
{
cin>>a[i];
}
m[n]=a[n];
ans=a[n-1]-a[n];//将m[n]与ans初始化
for(i=n-1;i>=1;i--)
{
m[i]=min(a[i],m[i+1]);
f[i]=a[i]-m[i+1];
if(f[i]>ans)
{
ans=f[i];//如果当前位置讨论的最小Wa-Wb小于之前求出的ans，就对ans赋新值
}
}
cout<
