首页 > 其他 > 详细

【leetcode】Best Time to Buy and Sell Stock

时间:2014-05-18 20:28:42      阅读:461      评论:0      收藏:0      [点我收藏+]

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.


题解:简单的动态规划题。用prices存储每天的股票价格,dp[i]表示第i天的最大利润,minmum表示遍历到当前为止prices中最小的元素。

那么在第i+1天有两种选择:

1.在这一天卖掉股票,那么显然可以获得的最大利润是prices[i+1]-minmum;

2.在这一天之前就把股票卖掉,那么可以获得的最大利润即使前i天可以获得最大利润。

dp[i] = max({dp[0],dp[1],...,dp[i]},prices[i+1]-minmum)

其实上述的dp数组也不需要,只要一个profit变量记录到当前为止可以获得最大的利润就可以了。

代码如下:

bubuko.com,布布扣
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size() == 0)
            return 0;

        int Profit = 0;
        int minmum_price = prices[0];

        for(int i= 1;i < prices.size();i++){
            if(prices[i] < minmum_price)
                minmum_price = prices[i];
            if(prices[i]-minmum_price > Profit)
                Profit = prices[i]-minmum_price;
        }

        return Profit;
    }
};

int main(){
    vector <int> prices;
    prices.push_back(3);
    prices.push_back(3);
    prices.push_back(5);
    prices.push_back(0);
    prices.push_back(0);
    prices.push_back(3);
    prices.push_back(1);
    prices.push_back(4);

    Solution s;
    cout <<s.maxProfit(prices)<<endl;
}
bubuko.com,布布扣

 

 

【leetcode】Best Time to Buy and Sell Stock,布布扣,bubuko.com

【leetcode】Best Time to Buy and Sell Stock

原文:http://www.cnblogs.com/sunshineatnoon/p/3732428.html

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