首页 > 其他 > 详细

<LeetCode OJ> 121. Best Time to Buy and Sell Stock

时间:2016-01-15 17:43:35      阅读:217      评论:0      收藏:0      [点我收藏+]

121. Best Time to Buy and Sell Stock

My Submissions
Total Accepted: 81473 Total Submissions: 234230 Difficulty: Medium

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.

Subscribe to see which companies asked this question

Show Similar Problems


分析:

思路首先:动态规划
遍历数组时记录当前价格以前的最小价格curMin,记录昨天能够获得的最大利润maxProfit
对于今天,为了能获得此刻的最大利润,显然只能卖,或者不做任何操作
如果不做任何操作,显然还是昨天maxProfit
如果卖掉今天天的股票,显然prices[i]-curMin

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1)
            return 0;
        int curMin=prices[0];
        int maxProfit=0;
        for(int i=1;i<prices.size();i++)
        {
            maxProfit=max(maxProfit,prices[i]-curMin);
            curMin=min(curMin,prices[i]);//获得历史最小价格的股票
        }
        return maxProfit;
    }
};



注:本博文为EbowTang原创,后续可能继续更新本文。如果转载,请务必复制本条信息!

原文地址:http://blog.csdn.net/ebowtang/article/details/50524380

原作者博客:http://blog.csdn.net/ebowtang


<LeetCode OJ> 121. Best Time to Buy and Sell Stock

原文:http://blog.csdn.net/ebowtang/article/details/50524380

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!