[leetcode]121. 買賣股票的最佳時機(Best Time to Buy and Sell Stock)C++代碼實作

1，題目描述

2，題目分析

動态規劃 前i天的最大收益 = max{ 前i - 1天的最大收益，第i天的價格 - 前i - 1天中的最小價格 }

思路還是挺清晰的，還是DP思想：

1. 記錄【今天之前買入的最小值】
2. 計算【今天之前最小值買入，今天賣出的獲利】，也即【今天賣出的最大獲利】
3. 比較【每天的最大獲利】，取最大值即可

3，代碼實作

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //動态規劃 前i天的最大收益 = max{ 前i - 1天的最大收益，第i天的價格 - 前i - 1天中的最小價格 }
	if (prices.size() <= 1)
		return 0;
	int minValue = prices[0], maxValue = 0;
	for (int i = 1; i < prices.size(); i++) {
		maxValue = max(maxValue, prices[i] - minValue);
		minValue = min(minValue, prices[i]);
	}
	return maxValue;
        
    }
};