題目描述

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

題目分析

對題目進行分析可知，買賣股票的最佳時機是由之前買或不買的狀態決定的，而之前買或不買又由更早的狀態決定的。因此，可以通過動態規劃的思路來分析。

1. 更新前i天的最低價格；
2. 由于需要使得利益最大化，因此，使用dp[i]表示前i天的最大利潤；
3. 且dp[i]等于dp[i?1] 和第 i天賣出的最高利潤中的最大值 。

Code

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