神刀安全网

C/C++ Coding Exercise – Best Time to Buy and Sell Stock

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.

Submit your solution : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Related puzzle: Buy and Sell Stock Multiple Times .

DP Version 1

Dynamic Programming (DP) stores the results of previous state. We keep recording the accumulated price changes and store the maximum one-pass.

class Solution { public:     int maxProfit(vector<int>& prices) {         int n = prices.size();         if (n < 2) {             return 0;         }         int r = 0; // max profit         int c = 0; // accumulated changes         for (int i = 1; i < n; i ++) {             c += prices[i] - prices[i - 1];             if (c < 0) c = 0;             if (c > r) r = c;         }         return r;     } };
class Solution { public:     int maxProfit(vector<int>& prices) {         int n = prices.size();         if (n < 2) {             return 0;         }         int r = 0; // max profit         int c = 0; // accumulated changes         for (int i = 1; i < n; i ++) {             c += prices[i] - prices[i - 1];             if (c < 0) c = 0;             if (c > r) r = c;         }         return r;     } };

FOr example, input [5 1 2 4 7],

i r c 0 0 0 1 0 0 r = -1 so reset to zero 2 1 1 3 3 3 4 6 6
i r c 0 0 0 1 0 0 r = -1 so reset to zero 2 1 1 3 3 3 4 6 6

DP Version 2

The above DP may not seem easy to understand. However, we can rewrite it slightly differently. The maximum profit equals the max(sell) – min(buy) so we can keep the min sell price and update the max(price[i] – min).

class Solution { public:     int maxProfit(vector<int>& prices) {         int n = prices.size();         if (n < 2) {             return 0;         }         int r = 0;         int m = prices[0];         for (int i = 0; i < n; i ++) {             r = max(r, prices[i] - m);             m = min(prices[i], m);         }         return r;     } };
class Solution { public:     int maxProfit(vector<int>& prices) {         int n = prices.size();         if (n < 2) {             return 0;         }         int r = 0;         int m = prices[0];         for (int i = 0; i < n; i ++) {             r = max(r, prices[i] - m);             m = min(prices[i], m);         }         return r;     } };

–EOF–

GD Star Rating

loading…

321 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C/C++ Coding Exercise – Best Time to Buy and Sell Stock

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮