What is the algorithm and underlying structure of this recursive DP algorithm about buying and selling stock?

Question

I have spent about 3 hours trying to figure this out, but I fail to understand two lines of code:

b[j]     = _max(b[j],     s[j] - prices[i]);
s[j + 1] = _max(s[j + 1], b[j] + prices[i]);

The problem that the following code is a DP solution to is: 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.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2

Output: 2

Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: [3,2,6,5,0,3], k = 2

Output: 7

Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

int _max(int a, int b) {
    return a > b ? a : b;
}
int all_profits(int* prices, int pricesSize) {
    int i, d, p;

    p = 0;
    for (i = 1; i < pricesSize; i ++) {
        d = prices[i] - prices[i - 1];
        p = d > 0 ? p + d : p;  // get it as long as it is a profit!
    }

    return p;
}
int maxProfit(int k, int* prices, int pricesSize) {
    int *b, *s, *buff, i, j, p;

    if (pricesSize < 2) return 0;

    if (k >= pricesSize / 2) return all_profits(prices, pricesSize);

    buff = malloc((2 * k + 1) * sizeof(int));
    //assert(buff);
    b = &buff[0];
    s = &buff[k];

    for (i = 0; i < k; i ++) {
        b[i] = 0x80000000;  // min integer
        s[i] = 0;
    }
    s[k] = 0;

    for (i = 0; i < pricesSize; i ++) {
        for (j = 0; j < k; j ++) {
            // profit on buy is current buy or last sale minus today's price
            b[j]     = _max(b[j],     s[j] - prices[i]);
            // profit on sale is current sale or last buy plus today's price
            s[j + 1] = _max(s[j + 1], b[j] + prices[i]);
        }
    }

    p = s[k];

    free(buff);

    return p;
}

I understand all of the code except for the two lines mentioned at the beginning:

What is the purpose of the buff array? The buff array is divided into two parts, one with b and the other with s. From what I understand, s[n] is the max profit you can make on the nth day. I have no idea what b is doing.
Why are we doing MAX of b[j] = _max(b[j], s[j] - prices[i]);, should the buying price not be the lowest? Why is b[j] the max of these two things? What is s[j] - prices[i]?
This probably also has to do with the algorithm but why this statement: s[j + 1] = _max(s[j + 1], b[j] + prices[i]); What is b[j] + prices[i] doing in this expression and what does it mean?
Why are we going through each day k times: for (j = 0; j < k; j ++) {?

I have spent a lot of time (3 hours) thinking about this solution and comparing it to other DP problems, but no luck. I compared it to longest increasing subsequence DP problem and how you're supposed to "Let length(k) denote the length of the longest increasing subsequence that ends at position k" and tried to apply that logic to arrays here, but no luck.

Thank you for any help.

גלעד ברקן גלעד ברקן · Accepted Answer · 2019-08-02T02:28:52

Consider that we would like to consider each price (or day) as either a buying day or a selling day to arrive at the best choices. The b list is considering each day as a buy day and the s list as a sell day. Now we just implement the logic. What might be slightly confusing is that because s is updated at j + 1, for the s list, j is the day before.

The best kth buy day for the price at i is either what we already have as the kth buy day or we buy, which equals the (k-1)th best sell day (that's the confusing s[j]) subtracted by the buying price since we just bought!

b[j] = _max(b[j], s[j] - prices[i]);

The best kth sell day for the price at i is either what we already have as the kth sell day or the best kth buy day (since a kth transaction has both a buy and a sell) plus today's price since we just earned it selling a stock!

s[j + 1] = _max(s[j + 1], b[j] + prices[i]);

Update

Per OP's request, here's an example: [5, 20, 15, 100, 35] k = 2.

b represents the most profit at
the jth buy considering prices up to i:
max(b[j], s[j] - prices[i])

s represents the most profit at
the jth sell (index j+1 in s) considering prices up to i:
max(s[j + 1], b[j] + prices[i])

note that when j = 0, s[j] (the sell before the first buy)
is always 0

prices[0]:
  j:  0     1
  b:  -5    -5 // max(-Inf, 0 - 5), max(-Inf, 0 - 5)
  s:  0     0  // max(0, -5 + 5), max(0, -5 + 5)

prices[1]:
  j:  0     1
  b:  -5    -5 // max(-5, 0 - 20), max(-5, 15 - 20)
  s:  15    15 // max(0, -5 + 20), max(0, -5 + 20)

prices[2]:
  j:  0    1
  b:  -5   0   // max(-5, 0 - 15), max(-5, 15 - 15)
  s:  15   15  // max(15, -5 + 15), max(15, 0 + 15)    

prices[3]:
  j:  0    1
  b:  -5   0   // max(-5, 0 - 100), max(0, 0 - 100) 
  s:  95   100 // max(15, -5 + 100), max(15, 0 + 100)

prices[4]:
  j:  0    1
  b:  -5   60  // max(-5, 0 - 35), max(0, 95 - 35)
  s:  95   100 // max(95, -5 + 35), max(100, 60 + 35)

What is the algorithm and underlying structure of this recursive DP algorithm about buying and selling stock?

1 Answers

Update