問題描寫

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.

Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

問題分析

動態計劃問題

假定f(i)是第i天能拿到的最大利潤，初始為0；minPrice是第i天之前的最低股價，初始為prices[0]，也就是假定第1天就買入股票

到第i+1天時，最大利潤為f(i+1)，則f(i+1)=max(f(i), prices[i+1]-minPrice)，也就是如果今天的價格與之前的最低股價的差值比前1天的利潤大，就采取新方案，也就在最低股價時買入，在今天賣出；否則就不動，繼續持有股價，所以會有今天的最大利潤=昨天的最高利潤，即f(i+1) = f(i)；然后更新最低股價，minPrice = min(prices[i+1], minPrice).

代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=0) return 0;
        int f=0, f1=0; // f(i) 表示第 i 天時的最大利潤，初始為0，此處f表示f(i), f1表示f(i⑴) 
        int buyPrice = prices[0]; // 之前買入的價格，假定第1天就買入 
        for(int i=1;i<prices.size();i++) {
            f1 = f = max(f1, prices[i]-buyPrice);
            buyPrice = min(prices[i], buyPrice);
        } 
        return f;
    }
};