Isn't `121. Best Time to Buy and Sell Stock` a Greedy algorithm?

[Vandivier]

It's tagged as DP

I guess we can say "Greedy algos are a special case of DP" but I would still expect both tags to be on the problem

[seanprashad]

Hey @Vandivier 👋🏽

We actually had this discussion recently over here: https://github.com/seanprashad/leetcode-patterns/pull/129. It's been a very long time since I've solved this question but skimming over recent comments mention that this is a modified version of Kadane's algo. I'm totally open to adding Greedy to this question but would first appreciate being linked to a clear explanation and solution!

[Vandivier]

Love your openness here. Let's start with a quick technical solution:

const maxProfit = prices => {
    let maxProfitFound = 0;
    let currMinBuy = prices[0];

    if (prices.length < 2) {
        return maxProfitFound;
    }

    for (let i = 1; i < prices.length; i++) {
        const currPrice = prices[i];
        currMinBuy = Math.min(currMinBuy, currPrice);
        maxProfitFound = Math.max(maxProfitFound, currPrice - currMinBuy);
    }

    return maxProfitFound;
}

Greedy algorithms can be defined as any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. You can see that is what we are doing here.

Depending on how we define DP, greedy algos are either a subset or an alternative approach. Let's define DP as any problem that applies a meta program to many subroutine solutions, then we can see that any greedy algorithm could be considered DP with a trivial meta program such as take latest, highest, smallest, etc from subroutine results. In this case, maxProfitFound.

On the other hand, if we consider DP as specifically those problems where the local optima do not lead to global optima, eg the coin change problem, we can see DP as an exclusive pattern compared to greedy algos instead of a superset.

[seanprashad]

Love your openness here. Let's start with a quick technical solution:

const maxProfit = prices => {
    let maxProfitFound = 0;
    let currMinBuy = prices[0];

    if (prices.length < 2) {
        return maxProfitFound;
    }

    for (let i = 1; i < prices.length; i++) {
        const currPrice = prices[i];
        currMinBuy = Math.min(currMinBuy, currPrice);
        maxProfitFound = Math.max(maxProfitFound, currPrice - currMinBuy);
    }

    return maxProfitFound;
}

Greedy algorithms can be defined as any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. You can see that is what we are doing here.

Depending on how we define DP, greedy algos are either a subset or an alternative approach. Let's define DP as any problem that applies a meta program to many subroutine solutions, then we can see that any greedy algorithm could be considered DP with a trivial meta program such as take latest, highest, smallest, etc from subroutine results. In this case, maxProfitFound.

On the other hand, if we consider DP as specifically those problems where the local optima do not lead to global optima, eg the coin change problem, we can see DP as an exclusive pattern compared to greedy algos instead of a superset.

Thank you for walking me through this - your logic was easy to follow at each step! I'll go ahead and reopen & merge #129 as to give credit to the original author and mark this as closed. Cheers! 😁

[seanprashad]

Updated, thanks again!