Example: Stock Buy Sell - rFronteddu/general_wiki GitHub Wiki

You are given stock prices on several days and have to get the max profit by doing at most k transactions. Furthermore, transactions cannot happen in parallel.

Strategy:

• i: number of transactions
• j: day
• t[i,j] = max(
  • t[i,j-1] value by not doing a transaction on day j
  • p[j] - p[m] + t[i-1,m] best you can get by completing a transaction on day m. Note that we have to find m = 0..j-1

---	0	1	2	3	4	5	6	7
---	2	5	7	1	4	3	1	3
0	0	0	0	0	0	0	0	0
1	0	3	5	5	5	5	5	5
2	0	3	5	5	8	8	8	8
3	0	3	5	5	8	8	8	10

While we test the relation, we notice that we don't really need to check all the values between 0 and j-1

Consider d[2,3]

• m=0 => T[1,0] - price[0] + price[3]
• m=1 => T[1,1] - price[1] + price[3]
• m=2 => T[1,2] - price[2] + price[3]

Consider d[2,4]

• m=0 => T[1,0] - price[0] + price[4]
• m=1 => T[1,1] - price[1] + price[4]
• m=2 => T[1,2] - price[2] + price[4]
• m=3 => T[1,3] - price[3] + price[4]

For each j, we can keep track of the maxDiff and update it with the new value of m=j-1 if the new one is larger

• d[i,j] = p[j] + max(maxDiff, t[i-1,j-1] - p[j-1])

// p: stock prices per day
// tr: number of transactions
// p: [0..n]
stock(p, tr)
    let d[0..tr, 0..p.len-1]
    for i = 1 to tr
        maxDiff = -inf
        for j = 0 to p.len-1
            // m can only get to j-1, so the latest m to test is j-1
            c = d[i-1, j-1] - p[j-1]
            if c > maxDiff
                maxDif = c
            d[i,j] = max(d[i, j-1], p[j] + maxDiff)

    i = tr
    j = x.len-1
    l = []
    while i > 0 && j > 0
        // find where current number comes from
        if d[i, j] == d[i,j-1]
            j--
        else 
            sellDay = j
            buyDay = j--
            prevProfit = d[i, j] - p[sellDay]
            while (prevProfit !=  d[i-1, j] - p[buyDay]) {
                buyDay--
            }
            l.insert(0, (buyDay, sellDay))
    print ("Max profit: " + d[tr, p.len-1])
    return l