41. 计算最大利润

一. 问题

外汇交易可以通过兑换不同国家的货币赚取汇率差。比如1美元兑换100日元时购入1000美元，然后等汇率变动到1美元兑换108美元时再卖出，这样就可以赚取（108 - 100）× 1000 = 8000日元。

现在请将某货币在 t 时刻的价格 R_t （t = 0, 1 , 2, ..., n - 1）作为输入数据，计算出价格差 R_j - R_i (其中j > i) 的最大值。

输入：第一行输入整数 n 。接下来 n 行依次给整数R_t （t = 0, 1 , 2, ..., n - 1）赋值。

输出：在单独 1 行中输出最大值。

限制：2 ≤ n ≤ 200000， 1 ≤ R_t ≤ 10⁹

输入示例1：6 5 3 1 3 4 3

输出示例1：3

输入示例2：3 4 3 2

输出示例2：-1

二.思路

首先，我们可以的到一组数据，这组数据代表货币在某时刻的价格。按照题目，我们需要获得最大利润。当买入时取最小值，卖出时取最大值，此时利润最大，为二者的差值。我们需要注意到，结果是一个值，所以只需要考虑令这个值最大化就行，而不用管买入时的价格之间的高低。

举个例子，情况1：买入2，卖出10，差值为8.情况2：买入1，卖出6，差值为5。我们只需要取这个最大的差值8，而不用管买入的最低价。

还需要注意的是，给定数据是按照时间排列的，只能用后面的汇率，减去前面的汇率，这样所得差值才有意义。

三.代码实现

解法1：

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 void fill_data(vector<int> &data, int n) {
 7     int temp_data;
 8     for (int i = 0; i < n; ++i) {
 9         cin >> temp_data;
10         data.push_back(temp_data);
11     }
12 }
13 
14 int cal_max_profit(const vector<int> &data) {
15     const int min_value = -200000;
16     int max_profit = min_value;
17 
18     for (int j = 1; j < data.size(); ++j) {
19         for (int i = 0; i < j; ++i) {
20             max_profit = max(max_profit, data[j] - data[i]);
21         }
22     }
23 
24     return max_profit;
25 }
26 
27 int main() {
28     int n = 0;
29     vector<int> data;
30     cin >> n;
31     fill_data(data, n);
32     int result = cal_max_profit(data);
33     cout << result << endl;
34 
35     return 0;
36 }

说明：在这种算法中，我们利用一个外层循环，控制靠后面的一个数，再用一个内层循环，控制靠前面的一个数，依次计算差值，看看与原来的差值谁大，如果新的差值大，那么就用新差值替换原差值。这样属于暴力算法，做了很多的无用功。我们没有必要对每一个靠后的数，再计算一次差值。

解法2：

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 void fill_data(vector<int> &data, int n) {
 7     int temp_data;
 8     for (int i = 0; i < n; ++i) {
 9         cin >> temp_data;
10         data.push_back(temp_data);
11     }
12 }
13 
14 void print_data(const vector<int> &data) {
15     for (auto &x : data) {
16         cout << x << " ";
17     }
18     cout << endl;
19 }
20 
21 int max_profit(const vector<int> &data) {
22     int result = -20000;
23     int min_value = data[0];
24 
25     for (int i = 1; i < data.size(); ++i) {
26         result = max(result, data[i] - min_value);
27         min_value = min(min_value, data[i]);
28     }
29 
30     return result;
31 }
32 
33 int main() {
34     int n = 0;
35     cin >> n;
36 
37     vector<int> data;
38     fill_data(data, n);
39     print_data(data);
40 
41     int result = max_profit(data);
42     cout << result << endl;
43 
44     return 0;
45 }

说明：在这种算法中，我们可以看出时间复杂度为O(n), 只需要遍历数据一次，即可得出结果。如同前面举的例子一样，最小值和最大值之间的差，才是我们最关心的。只需要从前向后遍历，找到一个最小值，和一个最大的差，记录下来即可。用这种手法，就能避免二重循环。