Question

Formatted question description: https://leetcode.ca/all/121.html

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.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁴

Algorithm

Traverse the array once, use a variable to record the minimum value of the traversed number, and then calculate the most profit each time the difference between the current value and this minimum value, and then select the larger profit each time to update. When the traversal is completed, the current profit is the desired.

Code

public class Best_Time_to_Buy_and_Sell_Stock {


    public class Solution_optimize {
        public int maxProfit(int[] prices) {
            int res = 0, buy = Integer.MAX_VALUE;
            for (int price : prices) {
                buy = Math.min(buy, price);
                res = Math.max(res, price - buy);

//                // also working
//                res = Math.max(res, price - buy);
//                buy = Math.min(buy, price);

            }
            return res;
        }
    }

	public class Solution {
	    public int maxProfit(int[] prices) {
	        if (prices == null || prices.length == 0) {
	            return 0;
	        }

	        int[] profit = new int[prices.length];
	        for (int i = 1; i < prices.length; i++) {
	            profit[i] = prices[i] - prices[i - 1];
	        }

	        // find maximum subarray
	        int max = profit[0]; // profit[0]==1
	        int sum = profit[0];
	        for (int i = 1; i < profit.length; i++) {
	            sum = sum + profit[i];
	            max = Math.max(max, sum);

	            if (sum < 0) {
	                sum = 0;
	            }
	        }

	        return max;

	    }
	}
}

############

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0, mi = prices[0];
        for (int v : prices) {
            ans = Math.max(ans, v - mi);
            mi = Math.min(mi, v);
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minVal = INT_MAX, ans = 0;
        for (int p : prices) {
            minVal = min(minVal, p);
            ans = max(ans, p - minVal);
        }
        return ans;
    }
};

'''
>>> import math
>>> a = math.inf
>>> a
inf

>>> x = float('-inf')
>>> y = float('inf')
>>> print(x < y)  # Output: True
True
>>>
>>> z = -math.inf
>>> x==z
True

'''
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans, mi = 0, inf
        for v in prices:
            mi = min(mi, v)
            ans = max(ans, v - mi)
        return ans

############

class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if not prices:
      return 0
    ans = 0
    pre = prices[0]
    for i in range(1, len(prices)):
      pre = min(pre, prices[i])
      ans = max(prices[i] - pre, ans)
    return ans

func maxProfit(prices []int) (ans int) {
	mi := prices[0]
	for _, v := range prices {
		ans = max(ans, v-mi)
		mi = min(mi, v)
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

function maxProfit(prices: number[]): number {
    let ans = 0;
    let mi = prices[0];
    for (const v of prices) {
        ans = Math.max(ans, v - mi);
        mi = Math.min(mi, v);
    }
    return ans;
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
    let ans = 0;
    let mi = prices[0];
    for (const v of prices) {
        ans = Math.max(ans, v - mi);
        mi = Math.min(mi, v);
    }
    return ans;
};

class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($prices) {
        $win = 0;
        $minPrice = $prices[0];
        $len = count($prices);
        for ($i = 1; $i < $len; $i++) {
            $minPrice = min($minPrice, $prices[$i]);
            $win = max($win, $prices[$i] - $minPrice);
        }
        return $win;
    }
}

public class Solution {
    public int MaxProfit(int[] prices) {
        int ans = 0, mi = prices[0];
        foreach (int v in prices) {
            ans = Math.Max(ans, v - mi);
            mi = Math.Min(mi, v);
        }
        return ans;
    }
}

impl Solution {
    pub fn max_profit(prices: Vec<i32>) -> i32 {
        let mut res = 0;
        let mut min = i32::MAX;
        for price in prices {
            res = res.max(price - min);
            min = min.min(price);
        }
        res
    }
}

121 - Best Time to Buy and Sell Stock

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions