# 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.

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