LeetCode 121 Best Time to Buy and Sell Stock解析（股票買入賣出的最佳時間）

LeetCode 121 Best Time to Buy and Sell Stock解析（股票買入賣出的最佳時間）

翻譯

話說你有一個數組，其中第i個元素表示在第i天的股票價格。

如果你被只被允許最多一次交易（例如，買入然後賣出一個股票），設計一個算法並找出最大利潤。

原文

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), 
design an algorithm to find the maximum profit.

分析

首先設定最大利潤和最小利潤：

如果當前這一天的股票價格比最低價格還小，那就把最低價格設置為這一天的股票價格。

為什麼要算這個價格了，當然是為了算最大利潤鋪路了。

如果最大利潤比當天價格減掉最低價格還要低，那就把最大利潤設置成當天價格減去最低的價格。

代碼

class Solution {
public:
    int maxProfit(vector& prices) {
        size_t size = prices.size();
        if (size <= 1) return 0;
        int min = INT_MAX, max = INT_MIN;
        for (int i = 0; i < size; ++i) {
            if (prices[i] < min)
                min = prices[i];
            if (max < prices[i] - min)
                max = prices[i] - min;
        }
        return max;
    }
};