题目描述
applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。
applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：
1. 睡（把）觉（妹）。
2. 以当天的价格作为成交价买入1股“塞帕思”的股票。
3. 以当天的价格作为成交价卖出1股“塞帕思”的股票。
最初applepi不持有该股票。现在你需要计算出在最优策略下，N天后applepi能够获得的最大利润。为了维护森林的和平，本着清仓甩锅的原则，在N天的交易结束后applepi也不能持有“塞帕思”的股票。为了更方便进行测试，applepi想知道如果他只进行一次买和一次卖的操作，他最多能赚多少钱。
【输入格式】
每个测试点包含若干组数据，以EOF结尾。对于每组数据：
第一行1个整数N。
第二行N个正整数，相邻两个整数之间用1个空格隔开，表示每一天股票的价格。
【输出格式】
对于每组数据，首先按样例所示的格式“Case #k:”输出该组数据的编号，然后输出一个整数，表示applepi最大能够获得的利润。
【样例】
样例输入1
6
2 6 7 3 5 6
8
1 2 3 4 5 6 7 8
样例输出1
Case #1: 5
Case #2: 7
样例输入2
10
15831 47573 60015 51368 32460 34125 43074 75172 54014 93578
样例输出2
Case #1: 77747
【数据规模与约定】
对于50%的数据，1≤N≤1000。
对于100%的数据，1≤N≤100000，股票价格不超过100000，每个测试点至多包含5组数据。
题解
首先，假设在第 \(i\) 天卖出股票，则在前 \(i-1\) 天中必定有一天买入了股票。那么，为了实现利润最大化，就要使买入价与卖出价的差值最大化。所以，卖出价一定时，买入的股票价格为前 \(i-1\) 天中的最低价。
AC Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
int main()
{
int t = 0;
while (~scanf("%d", &n))
{
printf("Case #%d: ", ++ t );
int minx = INT_MAX, ans = INT_MIN;
// minx 记录前 i-1 天中股票最低价。
// ans 记录最大利润。
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
if (i != 1) ans = max(ans, max(a[i] - minx, 0));
minx = min(minx, a[i]);
}
printf("%d\n", ans);
}
return 0;
}