121.买卖股票的最佳时期.md

// 复习
// 此题虽然是个简单题，但比122.买卖股票的最佳时机-ii难想一些。属于简单题，但不好想。
// 首先要画出股票走势的折线图，然后找规律。最后发现规律是：
// dp[i]=max(dp[i−1],prices[i]−minprice)。可以尝试动态规划，也可以直接for遍历处理。
// 采用一些max、min，以及全局的累计手段，每前进一步要么更新、要么保持的思路做。

// 此题简单来说就是：for遍历每前进一步，答案要么保持不变，要么更新为更大的（当前点-目前的最小点）
// 比的是max_diff这个跨度的大小。

// 在遍历for的过程中，每走一步都处理，寻找max_diff。一开始max_diff为0，往后走的情况是，
// 如果遇到下坡，那max_diff保持不变；如果遇到上坡，那max_diff要么不变，要么更新成
// prices[i]-min_val，因此这可以看出，下坡的过程也需要一直更新min_val值。

// 其实上述上坡、下坡可以合并，那就是无论上坡下坡，每往前走一步，都更新min_val，然后也都
// 更新max_diff为max(max_diff,prices[i]-min_val)。当然，思考的时候，还是上下坡更直观一点。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_val = prices[0];
        int max_diff = 0;

        // 这种股票走势折现问题，往往容易出现每步的前后2个点，要么上坡要么下坡。
        // 这里考虑使用[i-1]和[i]来表示，for遍历跳过第0个点，从第1个点开始，不会越界。
        // 此外还有个好处，就是此时的i-1表示之前，i表示当前点。这比i+1表示当前点更直观。
        // [i-1]~[i]也能直观看出是上坡，还是下坡。
        for (int i = 1; i < prices.size(); i++) {
            // 下坡，更新最小值min_val。要么不变，要么更新。
            // if (prices[i - 1] > prices[i]) {
                min_val = min(min_val, prices[i]);
                // log排查下坡问题。
                // cout<<"down i:"<<i<<" min_val:"<<min_val<<endl;
            // 上坡，更新答案max_diff。要么不变，要么更新。
            // } else {
                int cur_diff = prices[i] - min_val;
                max_diff = max(max_diff, cur_diff);
                // log排查上坡问题。
                // cout<<"up i:"<<i<<" max_diff:"<<max_diff<<endl;
            // }
        }

        return max_diff;
    }
};