LeetCode 121 Best Time to Buy and Sell Stock(股票买入卖出的最佳时间)

  1. 云栖社区>
  2. 博客>
  3. 正文

LeetCode 121 Best Time to Buy and Sell Stock(股票买入卖出的最佳时间)

nomasp 2016-03-08 18:44:23 浏览307
展开阅读全文
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50814399

翻译

话说你有一个数组,其中第i个元素表示在第i天的股票价格。

如果你被只被允许最多一次交易(例如,买入然后卖出一个股票),设计一个算法并找出最大利润。

原文

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.

分析

首先设定最大利润和最小利润:

如果当前这一天的股票价格比最低价格还小,那就把最低价格设置为这一天的股票价格。

为什么要算这个价格了,当然是为了算最大利润铺路了。

如果最大利润比当天价格减掉最低价格还要低,那就把最大利润设置成当天价格减去最低的价格。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        size_t size = prices.size();
        if (size <= 1) return 0;
        int min = INT_MAX, max = INT_MIN;
        for (int i = 0; i < size; ++i) {
            if (prices[i] < min)
                min = prices[i];
            if (max < prices[i] - min)
                max = prices[i] - min;
        }
        return max;
    }
};

网友评论

登录后评论
0/500
评论
nomasp
+ 关注