题目背景:
作为一名成功人士，kk 也想大捞一笔，于是他选择了一种最好的方式——写书。 果不其然，kk 的书在投入市场之后非常畅销，于是在利益的驱使下，他决定要 “炒书”！
题目描述：
炒书和炒股类似，kk 已经提前知道了每一天的书价，从第 1 天到第 n 天分别记 为 … , 他每次只能同时持有一张股票。 书商看不惯kk 的行为，于是限制了 kk 的交易，当 kk 被限制时他最多只能买一 次书和卖一次书。 kk想知道他最多能赚多少钱？
输入格式：
第一行两个数：n、m 分别表示天数和是否限制交易（1 表示限制） 第二行 n 个数，第 i 个数是 ai
输出格式:
一个数表示最多的利润
![技术分享图片]()
6 0
1 3 2 0 7 9
11
数据范围：
所有数据均为非负整数
对于 30%的数据 n＜＝1000
对于 60%的数据 m＝1，n＜＝1000000
对于 100%的数据 m＝0，n＜＝1000000
书价不大于 1000
__________________________________________________________________________________________________________________________________________________________________________________________________________________
当 m = 1 时 思路：定义一个结构体，存放书价以及第几天（编号）。把结构体按书价从小到大排序。定义 i 从前往后找，j 从后往前找，判断是否符合要求（买的天数必须在卖的天数前面，也就是 a[i] 的编号 < a[j] 的编号）如果符合要求，求出 a[j] 和 a[i] 的差值，答案已经找到了，跳出循环。如果不符合要求，继续 i++ 或 j--。i++ 还是 j-- 取决于两个差值 a[j-1] - a[i] 和 a[j] - a[i+1] 的大小，哪个差值大就说明能哪个能赚更多的钱
当 m = 0 时 思路：一个循环，当 a[i+1] > a[i] 时，把它们的差值加入答案ans中
还看到了一种非常巧妙的方法，这种方法在 m = 1 时从 n 到 1 倒序循环，排除了 max 值在 a[i] 在左边的情况
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <cstdio>
5 using namespace std;
6 const int N=1e6+10;
7 int n,m;
8 long long ans,a[N];
9 int main(){
10 freopen("book.in","r",stdin);
11 freopen("book.out","w",stdout);
12 cin>>n>>m;
13 for(int i=1;i<=n;i++)cin>>a[i];
14 if(m){
15 long long mx=a[n];
16 for(int i=n-1;i;i--){
17 ans=max(ans,mx-a[i]);
18 mx=max(mx,a[i]);
19 }
20 }
21 else for(int i=2;i<=n;i++){
22 if(a[i]>a[i-1])ans+=a[i]-a[i-1];
23 }
24 cout<<ans<<endl;
25 return 0;
26 }
巧妙的方法
小测试 炒书
原文：https://www.cnblogs.com/frank06/p/10389503.html
