The best time to buy and sell stocks

The best time to buy and sell stocks

Given an array, its ith element is the price of a given stock on the ith day.

If you only allow one trade (buy and sell a stock once), design an algorithm to calculate the maximum profit you can make.

Note: You cannot sell a stock before you buy it.

Example 1:

Input:7.1.5.3.6.4]

Output:5

Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6- 1 = 5 。

Notice the profit can't be7- 1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.

Copy the code

Example 2:

Input:7.6.4.3.1]

Output:0

Explanation: In this case, no transaction is completed, so the maximum profit is0.

Copy the code

Source: LeetCode

Train of thought

The difficulty of this problem is simple, record a minimum price, and then make a difference with the daily price to maximize the profit.

var maxProfit = function (prices) {

  let max = 0;

  let minPrice = prices[0];

  for (let i = 1; i < prices.length; i++) {

    minPrice = Math.min(minPrice, prices[i]);

    let currentMax = prices[i] - minPrice;

    max = Math.max(max, currentMax);

  }

  return max;

};

Copy the code

Results:

  • 200/200 cases passed (104 ms)
  • Your runtime beats 29.94 % of javascript submissions
  • Each node in the linked list has 10000 entries in the linked list.

The best time to buy and sell stocks II

Given an array, its ith element is the price of a given stock on the ith day.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input:7.1.5.3.6.4]

Output:7

Explanation: In no2Day (stock price =1) time to buy, at No3Day (stock price =5), the trade can make a profit5- 1 = 4 。

Then, at No4Day (stock price =3) time to buy, at No5Day (stock price =6), the trade can make a profit6- 3 = 3 。

Copy the code

Example 2:

Input:1.2.3.4.5]

Output:4

Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5- 1 = 4 。

Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later.

Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.

Copy the code

Example 3:

Input:7.6.4.3.1]

Output:0

Explanation: In this case, no transaction is completed, so the maximum profit is0.

Copy the code

Tip:

1 <= prices.length <= 3A \ *10 ^ 4

0 <= prices[i] <= 10 ^ 4

Copy the code

Train of thought

This is also a simple question, a little more complicated than the last one, and you can buy and sell an infinite number of times.

The idea is to record a dynamic low price, then hit a profitable price, accumulate profits, and then switch the low price.

For example, [1,2,3,4,5], the lowest price is initially 1

  1. Comparing the lowest price 1 with the price 2 on the next day, profit 1 is found, and the sum of profit is 1. At this time, the lowest price needs to be converted into 2, because only those higher than 2 can obtain greater profits in the future
  2. Comparing the lowest price 2 with the price 3 on the third day, profit 1 is found, and the sum of profit is 2. At this point, the lowest price needs to be converted to 3
  3. The lowest price 3 is compared with the price 4 on the fourth day, and profit 1 is found. The sum of profit is 3. At this point, the lowest price needs to be converted to 4
  4. Comparing the lowest price 4 with the fifth day’s price 5, profit 1 is found, and the sum of profit is 4. At this point, the lowest price needs to be converted to 5
var maxProfit = function (prices) {

  // The cumulative sum of profits

  let sum = 0;

  // The current lowest price

  let min = prices[0];

  for (let i = 1; i < prices.length; i++) {

    // If the current price is higher than the current minimum, the profit accumulates

    if (prices[i] > min) {

      sum += prices[i] - min;

      // After accumulating, you need to switch to the lowest price

      min = prices[i];

    } else {

      // Switch when the current price is equal to or below the minimum price

      min = prices[i];

    }

  }

  return sum;

};

Copy the code

Take a closer look at the code above and finally optimize it:

var maxProfit = function (prices) {

  // The cumulative sum of profits

  let sum = 0;

  // The current lowest price

  let min = prices[0];

  for (let i = 1; i < prices.length; i++) {

    // If the current price is higher than the current low, the profit accumulates

    if (prices[i] > min) {

      sum += prices[i] - min;

    }

    // Switch when the current price is above, equal to, or below the minimum price

    min = prices[i];

  }

  return sum;

};

Copy the code

Results:

  • 200/200 cases passed (92 ms)
  • Your runtime beats 27.45 % of javascript submissions
  • Each node in the linked list has 10000 entries in the linked list.

The best time to buy and sell stocks III

Given an array, its ith element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input:3.3.5.0.0.3.1.4]

Output:6

Explanation: In no4Day (stock price =0) time to buy, at No6Day (stock price =3), the trade can make a profit30 = 3 。

Then, at No7Day (stock price =1) time to buy, at No8Day (stock price =4), the trade can make a profit4- 1 = 3 。

Copy the code

Example 2:

Input:1.2.3.4.5]

Output:4

Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5- 1 = 4 。

Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later.

Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.

Copy the code

Example 3:

Input:7.6.4.3.1]

Output:0

Explanation: In this case, no transaction is completed, so the maximum profit is0.

Copy the code

Train of thought

The problem is hard and not easy to solve.

If the maximum allowed is one transaction, then most people know how to solve it. So let’s convert this to “maximum allowed one trade.”

“Maximum profit sold at present” = “Price sold at this time” – “Minimum price bought”

Continue to deform:

“Maximum profit sold at present” = “Price sold at this time” – “Composite minimum price bought”

What is the “composite minimum price to buy”? This is the minimum (” buy price “-” last buy profit maximum “)

So we’re going to have to figure out a minimum of what we’re going to do

var maxProfit = function (prices) {

  let min1 = prices[0];

  let min2 = prices[0];

  let max1 = 0;

  let max2 = 0;

  for (let index = 1; index < prices.length; index++) {

    // The lowest price currently encountered

    min1 = Math.min(min1, prices[index]);

    // The maximum amount of money made on the first trade so far

    max1 = Math.max(max1, prices[index] - min1);

    // The current composite low price of the purchase (counting the profit of the previous trade)

    min2 = Math.min(min2, prices[index] - max1);

    // The highest profit currently sold

    max2 = Math.max(max2, prices[index] - min2);

  }

  return max2;

};

Copy the code

Results:

  • 200/200 cases passed (80 ms)
  • Your runtime beats 81.89 % of javascript submissions
  • Each node in the linked list (10000 MB)

Interesting algorithm to “open the turntable lock”

Interesting algorithm ‘climbing stairs’