问题

假设你有一个数组，其中的第i个元素表示一只股票在第i天的价格。

如果只允许你完成一次交易（即买入并卖出股票一次），设计一个找出最大利润的算法。

初始思路

和122一样，基于买入与卖出股票的最佳时机III中的分析很容易得出答案。由于只允许进行一次交易，本题更加简单，我们只需按III中的方法不断更新最大利润即可。

 class Solution {

     public:

         int maxProfit(std::vector<int> &prices)

         {

             return CaculateProfit(prices).profit;

         }

     private:

         struct Profit

         {

             Profit() : profit(), buyPrice(-), buyDay(), sellDay()

             {

             }

             int profit;

             int buyPrice;

             int buyDay;

             int sellDay;

         };

         Profit CaculateProfit(std::vector<int> &prices)

         {

             Profit currentProfit;

             Profit maxProfit;

             for(int day = ; day < prices.size(); ++day)

             {

                 if(currentProfit.buyPrice == -)

                 {

                     currentProfit.buyPrice = prices[day];

                     currentProfit.buyDay = day;

                     continue;

                 }

                 currentProfit.profit = prices[day] - currentProfit.buyPrice;

                 currentProfit.sellDay = day;

                 if(currentProfit.profit < )

                 {

                     currentProfit.buyPrice = prices[day];

                     currentProfit.buyDay = day;

                     currentProfit.profit = ;

                 }

                 if(currentProfit.profit > maxProfit.profit)

                 {

                     maxProfit = currentProfit;

                 }

             }

             return maxProfit;

         }

     };

maxProfit

巴特西

[LeetCode 121] - 买入与卖出股票的最佳时机(Best Time to Buy and Sell Stock)

问题

初始思路

最新文章

热门文章