首页 > 其他 > 详细

Leetcode 121. Best Time to Buy and Sell Stock

时间:2016-07-24 14:41:14      阅读:238      评论:0      收藏:0      [点我收藏+]

121. Best Time to Buy and Sell Stock

  • Total Accepted: 115636
  • Total Submissions: 313848
  • Difficulty: Easy

 

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

 

思路:DP。

方法一:对于第i天,找到[0,i-1]天买进的最低价格,从而得到第i天出售的最高价格。然后遍历i,得到最高的出售价格。

方法二:最大子序列和问题。

 

 

代码:

方法一:

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int n=prices.size(),i,maxprofit=0,minprice=INT_MAX;
 5         for(i=0;i<n;i++){
 6             if(maxprofit<prices[i]-minprice){
 7                 maxprofit=prices[i]-minprice;
 8             }
 9             if(minprice>prices[i]){
10                 minprice=prices[i];
11             }
12         }
13         return maxprofit;
14     }
15 };

 

 

方法二:

参考:

https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input

https://en.wikipedia.org/wiki/Maximum_subarray_problem

原文:

The logic to solve this problem is same as "max subarray problem" using Kadanes Algorithm. Since no body has mentioned this so far, I thought its a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

    public int maxProfit(int[] prices) {
        int maxCur = 0, maxSoFar = 0;
        for(int i = 1; i < prices.length; i++) {
            maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
            maxSoFar = Math.max(maxCur, maxSoFar);
        }
        return maxSoFar;
    }
*maxCur = current maximum value

*maxSoFar = maximum value found so far

 

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int>& prices) {
 4         int i,n=prices.size(),curprofit=0,maxprofit=0;
 5         for(i=1;i<n;i++){
 6             curprofit=max(0,curprofit+prices[i]-prices[i-1]);
 7             maxprofit=max(maxprofit,curprofit);
 8         }
 9         return maxprofit;
10     }
11 };

 

Leetcode 121. Best Time to Buy and Sell Stock

原文:http://www.cnblogs.com/Deribs4/p/5700663.html

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