Topic describes

Given an array prices, its ith element prices[I] represents the price of a given stock on day I. You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make. Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Their thinking

  1. Record [minimum purchase before today]
  2. Calculate the minimum purchase before today and the profit from selling today, also known as the maximum profit from selling today.
  3. Compare [maximum profit per day] and take the maximum

Code implementation

const maxProfit = function (prices) {
  const len = prices.length;
  if (len < 1) {
    return 0;
  }
  let min = prices[0]; let max = 0;
  for (let i = 1; i < len; i++) {
    max = Math.max(max, prices[i] - min);
    min = Math.min(min, prices[i]);
  }
  return max;
};
Copy the code

Complexity analysis

  1. Time complexity: O(n), only need to traverse once
  2. Space complexity: O(1)