枚举：股票问题

思路：枚举什么时候卖出

• 练习如何更新数值
• 如何暴力求解

题目1

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？
例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。
如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11

//O(n)
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        if (nums.empty()) return 0;
        for (int i = 1, minv = nums[0]; i < n; i ++ )
        {
            res = max(res, nums[i] - minv);
            minv = min(minv, nums[i]);
        }
        return res;
    }
};

//O(n^2)
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int res = 0;
        if (nums.empty()) return 0;
        for (int i = 1; i < n; i ++ )
            for(int j = 1; j < i; j ++)
            {
                int minv = nums[0];
                if (minv > nums[j]) minv = nums[j];
                res = max(res, nums[i] - minv);
            }
        return res;
    }
};

题目2
* Design an algorithm to find the maximum profit. You may complete at most two transactions

• 解法一

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        int profit1 = 0, profit2 = 0;
        int profit = 0;
        if (nums.empty()) return 0;
        //枚举什么时候第一次卖出
        for (int i = 1, minv1 = nums[0]; i < n; i ++ )
            //枚举第二次卖出的情况
            for(int j = i + 2, minv2 = nums[i + 1]; j < n; j ++)
            {
                if(minv1 > nums[i]) minv1 = nums[i]; //更新前i-1个数中的最小值i
                if(minv2 > nums[j]) minv2 = nums[j]; //更新前i+1到n个数中的最大值
                profit1 = nums[i] - minv1;
                profit2 = nums[j] - minv2;
                profit = max(profit, profit1 + profit2);
                //if (i == 5 && j == 6) cout << maxv << " " << profit2 << endl;
                //if (i == 5 && j == 7) cout << maxv << " " << profit2 <<  endl;
                cout << "第一次卖出: " << nums[i] << " " 
                << "minv1: " << minv1 << " " << "profit1: " << profit1 << endl;
                cout << "第二次卖出: " << nums[j] << " " 
                << "minv2: " << minv2 << " " << "profit2: " << profit2 << endl;
                cout << "profit: " << profit << endl; 
            }

        return profit;
    }
};

• 解法二

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int minv = INT_MAX;
        int maxv = INT_MIN;
        int profit1 = 0, profit2;
        int total_profit;
        vector<int> f(n, 0); //f[i]表示第一次卖出时的最大利润
        // 特判：
        if (prices.empty()) return 0;
        //枚举第一次卖出时的情况（可能不是最后一个卖出）
        for (int i = 0; i < n; i ++ )
        {
            //最大利润 = 卖出时的价格 - 卖出前的最小价格
            if (prices[i] < minv) minv = prices[i];
            profit1 = max(profit1, prices[i] - minv);
            f[i] = profit1;
        }

        //枚举第二次买入的情况（当前买入）
        total_profit = f[n - 1];
        for (int i = n - 1; i > 0; i -- )
        {
            //最大利润 = 买入后的最大价格 - 买入时的价格
            if (prices[i] > maxv) maxv = prices[i];
            profit2 = maxv - prices[i];
            //总共最大利润 = 只操作一次的最大利润 + 操作两次的最大利润
            total_profit = max(total_profit, f[i - 1] + profit2);
        }

        return total_profit;
    }
};
// 为什么 total_profit = max(f[n - 1], f[i - 1] + profit2); 这样写不可以？