Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Today, someone asked the written test encountered a question: the array from the right to the left to find the maximum difference, I think of the force button has a more classic question: the best time to buy and sell stocks

This problem is relatively simple, mainly through this problem gradually understand dynamic planning, greedy algorithms and other skills

There are a lot of official problem solutions, so the main idea is to provide the idea of doing the problem. How to optimize the solution from 123 to the end

First preliminary pass, and then optimization, first of all, there is a train of thought

  1. Default to a minimum, maximum, profit
  2. Make judgment by traversing, update minimum, maximum, profit
  3. Return the final result when traversal is complete
/** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { Let min = prices[0] let Max = prices[0] let res = 0 i < prices.length; i++) { if (min >= prices[i]) { min = prices[i] max = prices[i] } if(max <= prices[i]){ max = prices[i] } res = res > max-min ? Res: max-min} // Return final result after traversal return res};Copy the code

This is ok, but the code is not elegant enough and can be refined

Here I’m getting the results and updating them with max-min in traversal, but it can be calculated directly with profit

  1. So let’s get rid of Max. I don’t need Max here
  2. Then useMathfunctionFirst the ifThe judgment and content are replaced bymin = Math.min(min, prices[i])By the same logic
  3. Then put theSecond ifThe judgment and content are replaced byres = Math.max(res, prices[i] - min)By the same logic
  4. To get rid ofres = res > max-min ? res : max-min
  5. Return result
/** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { Let min = prices[0] let res = 0 for (let I = 1; i < prices.length; I ++) {min = Math. Min (min, prices[I]) res = Math. Max (res, prices[I] -min)}Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)