Algorithm to Determine the 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.

Dynamic Programming Algorithm: Best Time to Buy and Sell One Stock

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

Time complexity is O(N) – and space is constant.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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;
    }
};

This DP also runs at O(N) time and O(1) space.

Buy and Sell Stock Algorithms

• C/C++ Coding Exercise – Best Time to Buy and Sell Stock
• Greedy Algorithm Example – What is the Best Time to Buy and Sell Stock?
• Teaching Kids Programming – Best Time to Buy and Sell Stock (Buy and Sell Once – Three Algorithms)

–EOF (The Ultimate Computing & Technology Blog) —