Leetcode’s Best Time To Buy & Sell Stocks With Solution

Prompt

Here is the link to the Leetcode problem.

Solution 1: Greedy Algorithm Approach

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let buy = prices[0];
    let maxProfit = 0;

    for (let i=1; i<prices.length; i++){
        const gainedAmount = prices[i]-buy;
        if (buy > prices[i]){
            buy = prices[i];
        } else if (gainedAmount > maxProfit){
            maxProfit = gainedAmount;
        }
    }
    return maxProfit;
};

• Time Complexity: O(N). Where N is the size of prices array.
  Auxiliary Space: O(1)
• This uses the Kadane’s Algorithm. It is a dynamic programming technique used to find the maximum subarray sum in an array of numbers.
• The critical insight behind the Algorithm is to consider the maximum subarray sum ending at the current position and update it based on the previous maximum subarray sum.
• In the Kadane’s Algorithm, a max variable needs to be initialized. max variable with begin with the first element in the array. Then the for loop will begin with 1 because the first day to be able to sell would be at index 1 (the first different day from index 0).