Oggi vediamo il seguente esercizio di LeetCode:

You are given an array prices where prices[i] is the price of a given stock on the i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Possiamo risolvere questo problema tenendo traccia del prezzo minimo e aggiornando il profitto massimo durante la scansione, come nel codice proposto.

L’idea chiave è:

  • inizializziamo il prezzo minimo con il primo elemento dell’array
  • scorriamo l’array a partire dal secondo elemento
  • se troviamo un prezzo più basso, aggiorniamo il minimo e “resettiamo” la possibile vendita
  • altrimenti, consideriamo il prezzo corrente come possibile vendita
  • calcoliamo il profitto come differenza tra prezzo corrente e minimo
  • aggiorniamo il profitto massimo se troviamo un valore migliore
  • alla fine, se non è stato possibile ottenere profitto, restituiamo 0

Questo approccio permette di ottenere una complessità O(n), poiché analizziamo l’array una sola volta. Tuttavia, nel codice proposto vengono utilizzate variabili aggiuntive come le posizioni (minPos, maxPos) e controlli extra che rendono la soluzione più complessa del necessario: è sufficiente mantenere solo il minimo e il profitto massimo per ottenere lo stesso risultato in modo più semplice ed efficace.

/*
brute force :(
function maxProfit(prices: number[]): number {
    let max = 0;

    for(let i = 0; i < prices.length; i++){
        for(let j = i+1; j < prices.length; j++){
            if(max < prices[j] - prices[i]){
                max = prices[j] - prices[i]
            }
        }
    }

    return max;
};*/

function maxProfit(prices: number[]): number {
    let min = prices[0];
    let minPos = 0;
    let max = prices[1];
    let maxPos = 1;
    let maxProfit = max - min;

    for(let i = 1; i < prices.length; i++){
        if(min > prices[i]){
            min = prices[i];
            minPos = i;
            maxPos = -1
        }else if(maxPos == -1 || max < prices[i] && i > minPos){
            max = prices[i];
            if(maxProfit < max - min){
                maxProfit = max - min
            }
        }
    }

    if(maxPos == 0 || maxProfit < 0 || prices.length == 1){
        maxProfit = 0;
    }

    return maxProfit;
};

sol2.py

class Solution(object):

    def maxProfit_bruteforce(self, prices):

        """

        :type prices: List[int]

        :rtype: int

        """

        best_profit = 0

        for idx_buy in range(len(prices)):

            idx_sell = idx_buy + 1

            while idx_sell < len(prices):

                best_profit = max(best_profit, prices[idx_sell] - prices[idx_buy])

                idx_sell += 1

        return best_profit

 

    def maxProfit(self, prices):
        min_array = [0]*len(prices)
        max_array = [0]*len(prices)
        curr_min= prices[0]

        for idx_buy in range(len(prices)):
            curr_min = min(curr_min, prices[idx_buy])
            min_array[idx_buy] = curr_min

        curr_max= prices[-1]
        for idx_sell in range(len(prices))[::-1]:
            curr_max = max(curr_max, prices[idx_sell])
            max_array[idx_sell] = curr_max

        best_profit = 0
        for idx in range(len(prices)):
            best_profit = max(best_profit, max_array[idx]-min_array[idx])

        return best_profit

sol3.js

/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
    let max = 0;
    let currentIndex = 0;
    let minVal = prices[0];
    for(i = 0; i < prices.length; i++){
        if(prices[i] < minVal){
            minVal = prices[i];
            currentIndex = i;
        }
        if(prices[i]- prices[currentIndex] > max){
            max = prices[i]-prices[currentIndex];
        }
    }
    return max;
};

Se hai dubbi in merito non esitare a contattarci sui nostri social, saremo più che felici di risponderti :)