1. Title Description

Ii. Analysis of Ideas:

Find the maximum difference between two values in an array.

Again, the constraint: the difference must be the latter position minus the former position, and if less than zero, zero is returned,

The simplest cycle of violence, through a two-layer cycle, can achieve all the differences of comparison. Number of n (n – 1) / 2

var maxProfit = function (prices) {
  let max = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const diff = prices[j] - prices[i];
      // Error record: forgot to write Max the first time, not the first time pass
      max = Math.max(max, diff); }}return max;
};
Copy the code

Error: Run out of time limit

  • Time complexity: O(n^2); Comparison of then(n-1)/2Times;
  • Space complexity: O(1);

Why n times n minus 1 over 2? (n-1) + (n-2) + (n-3) … + 1, construct an identical forward sequence to calculate, 1 + 2 +… (n-1), the sum of the two expressions is n + n… N, there are n minus 1 of them, let’s call them n times n minus 1, minus 2 is the value of n times n minus 1 over 2. So n times n minus 1 over 2 times. That’s the idea of gauss summation.

To put it another way, if we want to maximize profit on day I, we must subtract the lowest price in the previous [0, i-1] element to maximize profit. Therefore, a variable can be used to record the smallest number in the traversal process. Maximum Profit: Current price – all-time low price.

var maxProfit = function (prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (let i = 0; i < prices.length; i++) {
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    } else if (maxProfit <  prices[i] - minPrice) {
      maxProfit =  prices[i] - minPrice
    }
  }

  return maxProfit;
};

Copy the code
  • Time complexity: O(n);
  • Space complexity: O(1);

Iii. Summary:

The key of this question is the direction of thinking, in the algorithm of the time to change several directions to think, without a word on the violence, feel when you enter the violence, the thinking will gradually solidify, to think in this direction, it is difficult to think of a better way. Instead, you should analyze what type of problem the problem is at the very beginning, and then think about the division according to the type, whether it can be solved in this way.

This is the simplest problem in the stock series. This study plan solves the stock series problem first. Come on!