【LeetCode】121. Best Time to Buy and Sell Stock

问题描写

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;
    }
};