Buy & Sell Stock with K Transactions

Writeup.js

/*
Pure recursive approach.
Branching factor of, at worst, a.length.
Yields O(len(a)^len(a)), which is about has bad as it gets...
*/
const stockWithKTransactionsRecursive = (k, a) => {

    const maxProfit = (i, k) => { // on the ith day, with k transactions remaining
        if(i <= 0) return 0; // if it's day 0, we can't make a profit since we need at least one previous day to buy on
        if(k === 0) return 0; // if we have no transactions remaining, just return 0;

        // if we have any transactions remaining
        let maxFromSaleOnDayi = 0; // let's work out the max profit we can make by selling on the ith day.
                                    // If we're going to sell on the ith day, we must have bought on day 0..i-1.
                                    // so let's work out which day we should have bought on.
        for(let j=0; j<i; j++){ // for each previous day j...
            // the profit we'd make from buying on day j and selling on day i is given by
            const profitFromBuyingAtJ = a[i] - a[j] + // the price on day i - price on day j
                                        maxProfit(j-1, k-1); // PLUS whatever we could make with k-1 transactions before day j-1.
            // We want the max possible profit we'd get from all Js so...
            maxFromSaleOnDayi = Math.max(maxFromSaleOnDayi, profitFromBuyingAtJ); // remember the best option
        }

        return  Math.max( // the best we can do on day i with k transactions is:
            maxFromSaleOnDayi, // the best we can get from selling on day i
            maxProfit(i-1, k) // or not selling on day i
        );
    };

    return maxProfit(a.length-1, k); // lets start at the end, with k transactions
};

/*
Notice, we can also do this in reverse. We don't have to start at the back. Look for the subtle changes in
this approach. I've *d the lines that have changed
*/
const stockWithKTransactionsRecursiveForward = (k, a) => {

    const maxProfit = (i, k) => { // on the ith day, with k transactions remaining
        if(i === a.length) return 0; // if we've run out of days, we can't make a profit
        if(k === 0) return 0; // if we have no transactions remaining, just return 0;

        // if we have any transactions remaining
        let maxFromBuyingOnDayi = 0; // let's work out the max profit we can make by *buying* on the ith day.
                                     // If we're going to buy on the ith day, we must sell on day i+1 or later
                                     // so let's work out which day we should have sell on.
        for(let j=i+1; j<a.length; j++){ // for each following day j...
            // the profit we'd make from buying on day i and selling on day j is given by
            const profitFromSellingOnDayJ = a[j] - a[i] + // the price on day j - price on day i
                                        maxProfit(j+1, k-1); // PLUS whatever we could make with k-1 transactions after day j+1.
            // We want the max possible profit we'd get from all Js so...
            maxFromBuyingOnDayi = Math.max(maxFromBuyingOnDayi, profitFromSellingOnDayJ); // remember the best option
        }

        return  Math.max( // the best we can do on day i with k transactions is:
            maxFromBuyingOnDayi, // the best we can get from buying on day i
            maxProfit(i+1, k) // or NOT buying on day i, but maybe buying later
        );
    };

    return maxProfit(0, k); // lets start at the front, with k transactions
};

/*
These are something like O(len(a)^len(a)), which is clearly terrible. 
Both these approaches have subtle improvements we can make, but lets ignore those for now and try memoizing.
Note the space of possible arguments to the inner function `maxProfit`.
- i is bounded by 0 to a.length-1.
- k is bounded by 0 to k.
So if we memoize, the maximum number of calls to maxProfit is a.length * k, so out overall TC goes down to
O(numberOfCallsToRecursiveFunction * TC of recursiveFunction)
O([a.length * k] * a.length)
O(k*a.length^2) // big improvement!

Since we're memoizing the calls, that costs space, which is
also just a.length * k (one space in an array for each call).

In most questions, this is a minimum 'passable' answer. I've taken the back-to-front approach but really, 
they're identical. 
*/
const stockWithKTransactionsMemoized = (k, a) => {
    // our memo table. Could just as well use a hash table but this is the convention.
    const memo = new Array(a.length).fill(0).map(() => new Array(k+1).fill(null));

    const maxProfit = (i, k) => {
        if(i <= 0 || k <= 0) return 0;

        if(memo[i][k] !== null) return memo[i][k];

        if(k > 0){
            let maxFromSaleOnDayi = 0;
            for(let j=0; j<i; j++){
                const profitFromBuyingAtJ = a[i] - a[j] + maxProfit(j-1, k-1);
                maxFromSaleOnDayi = Math.max(maxFromSaleOnDayi, profitFromBuyingAtJ);
            }
            return memo[i][k] =  Math.max(maxFromSaleOnDayi, maxProfit(i-1, k)); // remember the answer
        }

        return memo[i][k] = 0;
    };

    return maxProfit(a.length-1, k);
};

/*
Let's shorten that to a 'whiteboardable' length and hit 'submit'!
*/
const stockWithKTransactionsCompressed = (k, a) => {

    const memo = new Array(a.length).fill(0).map(() => new Array(k+1).fill(null));

    const maxProfit = (i, k) => {
        if(i <= 0 || k <= 0) return 0;
        if(memo[i][k] !== null) return memo[i][k];

        let maxIK = 0;
        for(let j=0; j<i; j++) maxIK = Math.max(maxIK, a[i] - a[j] + maxProfit(j-1, k-1));
        return memo[i][k] =  Math.max(maxIK, maxProfit(i-1, k));
    };

    return maxProfit(a.length-1, k);
};

/*
What?! Heap out of space!?

Well, there're too possible answers:
1. There's a more elegant greedy approach. 
2. MOAR optimization required!

I'm not smart enough to figure out (1) late at night, so let's try for 2. 
*/

/*
Since we're just filling up a table, we could get straight to the point with a
few for-loops. I translated the recursive answer into a "bottom-up" one and am
now just filling up a memo table. I always find this to be the hardest jump to
make but whatever... once you've got a memoized solution you're happy with it's
just a case of:
1. Figure out what order your memo table will be filled in by the recursion
2. Recreate that yourself

What I've done here is save O(depth of recursion) space, so I'm hoping our
problem will go away now.

Refactor, and hit submit.
*/
const stockWithKTransactionsTabulated = (k, a) => {
    if(!a.length || !k) return 0; // our recursive bases cases don't save us anymore so be careful

    const memo = new Array(a.length).fill(0).map(() => new Array(k+1).fill(null)); // same as last time

    // try to frame this the same way we did in the very first recursive approach.
    for(let kay=0; kay<=k; kay++){ // Given that we have k transactions...
        for(let i=0; i<a.length; i++){ /// on day i...
            if(kay === 0 || i === 0) { memo[i][kay] = 0; continue; } // base cases. No trx or no time to transact

            let maxIK = 0; // Track the best we can do today. If we want to sell today
            for(let j=0; j<i; j++){ // we must have bought on day j. The best we can get is
                maxIK = Math.max( // the max of
                    maxIK, // the best we've found so far, and
                    a[i] - a[j] + // the difference in price between days i and j +
                    ( j > 1 ? memo[j-1][kay-1] : 0) // the best we can get from selling before day j, with k-1 trx
                );
            }
            memo[i][kay] = Math.max(maxIK, ( i > 1 ? memo[i-1][kay] : 0)); // OR, not selling at all!
        }
    }

    return memo[a.length-1][k];
};

/*
Heap out of memory!? Leetcode is cruel today...

Alright. Remember those optimisations I said we had at the beginning that we left aside? Time to whip them out. 
*/
const stockWithKTransactionsTabulatedHardcore = (k, a) => {
    if(!a.length || !k) return 0;

    // Each transaction requires two days (one to buy, one to sell). So if a.length > 2k, we have
    // all the transactions we could want. So just try to greedily buy and sell at every opportunity.
    if(k > (a.length / 2) ){
        let profit = 0;
        for(let i = 1; i < a.length; i++){
            if(a[i] > a[i - 1]) profit += a[i] - a[i - 1];
        }
        return profit;
    }

    const memo = new Array(a.length).fill(0).map(() => new Array(k+1).fill(null)); // same as last time

    for(let kay=0; kay<=k; kay++){
        for(let i=0; i<a.length; i++){
            if(kay === 0 || i === 0) { memo[i][kay] = 0; continue; }

            let maxIK = 0;
            for(let j=0; j<i; j++){
                maxIK = Math.max(maxIK, a[i] - a[j] + ( j > 1 ? memo[j-1][kay-1] : 0));
            }
            memo[i][kay] = Math.max(maxIK, ( i > 1 ? memo[i-1][kay] : 0));
        }
    }

    return memo[a.length-1][k];
};

/*
Passes! But only beats 6%?!? :'(

Alright. Give up. Let's look at the solution...
*/