I. Title Description:

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.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can’t sell stocks before you buy them.

Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

Tip:
  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

Ii. Analysis of Ideas:

Just touch this topic, feel or quite simple, use the selection sort, two cycles can be done. Well, yes, it’s method one below.

Idea 1:

Given an array to maximize profit, let’s set a variableprofitSave the profit value. Buy before you sell and make a profit:Sell value - Buy value = profit. Find the maximum profit value in the array loop. So it takes two cycles, subtracting what you bought and what you saved from the value of the stockprofitCompare withprofitIs updatedprofitValue.

After writing the verification results, we found that:timeout!!!!!

emmm… Forced to rethink.

Idea 2:

Timeout is definitely because there’s too much data. Let’s see if we can do it in just one loop. In a cycle, I have to pick at least the highest sell value and the lowest buy value, and the buy value must precede the sell value. So, if you take the first value in the array, you can define it as the buying value min, and as you loop, you replace min with anything less than min. Prices [I] -min is used to compare the price of each day minus the lowest value of the previous day with the profit value, replacing profit if prices[I] -min is greater than the profit value. So you can maximize your profit. (My understanding is a little different from the official, I think it is a loop, take the smallest value of the array to the beginning of the day, not the smallest value in the array).

Iii. AC Code:

Method one:

function maxProfit(prices: number[]) :number {
  let profit: number = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      if(prices[j] - prices[i] > profit) { profit = prices[j] - prices[i]; }}}return profit;
}
Copy the code

Method 2:

function maxProfit(prices: number[]) :number {
    let profit: number = 0;
    let min: number = prices[0]; / / buy
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        }
        if(prices[i] - min > profit) { profit = prices[i] - min; }}return profit;
};
Copy the code

Iv. Summary:

Consider performance, optimization and so on when solving problems!! After checking letcode’s official solution, it is found that this question is indeed controversial. The code is correct, but the interpretation is a little different.

Leetcode. This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign.