数据结构与算法实验题 4.2 Who is the strongest
★实验任务
在神奇的魔法世界，召唤师召唤了一群的魁偶。这些魁偶排成一排，每个魁偶都有一个
战斗值。现在该召唤师有一个技能，该技能能对其中某个魁偶战斗值进行提高，增加的值为
排在该魁偶左边的战斗值大于它且离他最近的魁偶的战斗值（若该魁偶左边没有大于它的则
战斗值不变）。若有一排魁偶战斗值为 8 7 6 8 9 2 则对最后一个魁偶是用该技能的话则最
后一个魁偶战斗值变成 2+9=11。现在召唤师召唤了一排魁偶，从左到右战斗值都已知，召
唤师只能使用一次技能，现在让你进行选择其中一个魁偶使用技能，使得战斗值最大的魁偶
的战斗值最大。如上面一排魁偶战斗值为 8 7 6 8 9 2 若对第 3 个使用则最大为 13，对第
二个使用最大值为 15，所以最佳情况是对第二个魁偶使用该技能。
★数据输入
输入第一行为一个正整数 N (2 < N <= 100000)， 表示有 N 个魁偶排成一列。
第 2 行 N 个整数。第 i 个整数 ai 表示第 i 个魁偶战斗值为 ai（0<ai<=1000000）。
★数据输出
输出一行一个整数，表示最大战斗值。
输入示例
6
8 7 6 8 9 2
输出示例
15
水题。。。。。一直懒得做。
这题直接遇到小于等于当前的出栈就好（保证栈里的元素越栈底越大）
不过话说我用自己写的栈比STL快。
嗯哼。
#include<cstdio>
const int MAXN= 100000+10;
int data[MAXN];
struct stack
{
int d[MAXN];
int len; bool empty()
{
return len==0;
} int top()
{
return d[len];
} void pop()
{
len--;
} void push(int x)
{
d[++len]=x;
}
}s;
int main()
{
int n,i;
int ans=-99999;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&data[i]);
ans=ans>data[i]? ans:data[i];
} int temp;
for(i=0;i<n;i++)
{
while(!s.empty())
{
temp=s.top();
if(data[i] >= temp)
{
s.pop();
}
else
{
ans= ans>(temp+data[i])? ans: (temp+data[i]);
break;
}
}
s.push(data[i]); }
printf("%d\n",ans);
}