前言

這題是股票買賣系列的題目，與他類似的題目會是

122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown

題目敘述

題目難度： Easy
題目描述：給定一個陣列 prices，prices[i] 代表在第 i 天的股票價格。請選一天進買入股票，但在不同天賣出股票 (買賣股票不能在同一天，且須先買股票才能賣股票)，求股票的最大化收益。

解法

一開始的想法

一開始的想法複雜度其實比較高，就是透過一個迴圈來決定買入，透過另一個內部迴圈決定賣出，然後透過一個變數 maxValue 保存第 i 天買入然後第 j 天賣出的的最大股票收益值。但這樣的做法會導致 time limit excceded!

class Solution {
public:
    int maxProfit(vector<int>& prices){
        if(prices.size() < 2) return 0;
        int n = prices.size();
        int maxValue=0;

        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                maxValue = max(maxValue, prices[j] - prices[i] );
            }
        }
        return maxValue;
    }
};

我的解法

class Solution {
public:
    int maxProfit(vector<int>& prices){
        if(prices.size() < 2) return 0;
        int n = prices.size();
        int minValue = INT_MAX;
        int maxValue = 0;

        for(int i=0; i<n; i++){
            minValue = min(minValue, prices[i]);
            maxValue = max(maxValue, prices[i] - minValue);
        }
        return maxValue;
    }
};