首页 > 未分类 > #leetcode#股票的卖出买入时机问题

#leetcode#股票的卖出买入时机问题

2014年1月13日 sigma 发表评论 阅读评论

问题:

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.

抽象:

问题可抽象为,数组A,寻找i,j,使得 A[i]-A[j]最大,其中i>j.

最简单的算法,所有A[i],A[j]差的组合都列出来,共有nxn种,复杂度为O(n^2).其实这题有O(n)算法,只需要一遍遍历,遍历过程中记录最佳卖价(最高价)和最佳买价(最低价),需要注意的是由于卖必须在买前,因此,评判标准应该是差价。具体代码如下:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size()<2){
            return 0;
        }
        int sell=prices.at(1);
        int buy=prices.at(0);
        int sell_i=0;
        int buy_i=0;
        int max_profit=0;
        int final_max_profit=max_profit;
        for(int i=0;i<prices.size()-1;i++){
            max_profit+=(prices.at(i+1)-prices.at(i));

            if(max_profit<0&&i<(prices.size()-2)){
                buy_i=i+1;
                buy=prices.at(i+1);
                sell_i=i+2;
                sell=prices.at(i+2);
                max_profit=0;
            }
            else{
                sell_i=i+1;
            }
            if(max_profit>final_max_profit){
                final_max_profit=max_profit;
            }
        }
        return final_max_profit;
    }
};

由于OJ刚挂,以上代码未测试,

OJ链接:
http://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/

本文作者: Sigma    在新浪微博关注SigmaSigmaWeibo    RSS订阅本博客
本文链接: http://mblog.sigma.me/2014/01/13/leetcode-best-sell-best-buy.html
本博客采用知识共享署名—非商业性-禁止演绎使用3.0协议进行许可,转载请保留作者和原文链接。

分类: 未分类 标签:

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.

无觅相关文章插件,快速提升流量