SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The goal is to maximize profit by choosing the best day to buy and the best day to sell the stock. To achieve this, we need to track the lowest price seen so far and calculate the potential profit at each step by comparing the current price with this minimum price. The maximum profit will be the highest of these potential profits.

Approach

1. Initialize minn to the first price in the array. This variable will keep track of the lowest price seen so far.
2. Initialize profit to 0. This variable will keep track of the maximum profit seen so far.
3. Iterate through the array starting from the first price:
   • For each price, if it is lower than minn, update minn to this price.
   • Otherwise, calculate the potential profit by subtracting minn from the current price. If this profit is higher than the current profit, update profit.
4. Return the profit. If no profit can be made, profit will remain 0.

Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Space Complexity

The space complexity is O(1) since we are using only a few extra variables and not any additional space that scales with the input size.

Code

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        int imin=prices[0], res=0;
        for(auto &s: prices){
            res = max(res, s - imin);
            res = res>s-imin? res: s-imin;
            imin = imin<s?imin:s;
        }
        return res;

    }
};

Python

class Solution:
    def maxProfit(self, values: List[int]) -> int:
        minn = values.pop(0) 
        maxx = 0
        profit = 0
        for value in values:
            if value < minn:
                minn = value
                maxx = 0
            elif value > maxx:
                maxx = value
                if maxx-minn > profit:
                    profit = maxx-minn
                    
        return profit

Java

public class Solution {
    public int maxProfit(int prices[]) {
        if(prices==null || prices.length==0) return 0;
        int min = prices[0];
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if(prices[i]>min)
            {
                maxprofit=Math.max(maxprofit,prices[i]-min);
            }
            else
            {
                min=prices[i];
            }
            
        }
          
        return maxprofit;
    }
}

JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices.length === 0) return 0;

    let minn = prices[0];
    let maxx = 0;
    let profit = 0;
    
    for (let i = 1; i < prices.length; ++i) {
        if (prices[i] < minn) {
            minn = prices[i];
            maxx = 0;
        } else if (prices[i] > maxx) {
            maxx = prices[i];
            if (maxx - minn > profit) {
                profit = maxx - minn;
            }
        }
    }
    
    return profit;
};