国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 【LeetCode】121. Best Time to Buy and Sell Stock

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

来源:程序员人生   发布时间:2017-02-15 09:20:26 阅读次数:2087次

问题描写

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天能拿到的最大利润,初始为0minPrice是第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;
    }
};
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生