The best time to buy and sell stocks

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

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

Source: LeetCode link: leetcode-cn.com/problems/be… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Ii. Analysis of Ideas:

  1. What ideas does this question examine? What’s your thinking?

    My idea for this problem is to go through each set of prices and then evaluate the difference with each value that follows. The maximum difference is kept in the array RES, and then find the maximum value of the array RES. But I think it’s going to run over.

    And then the second train of thought, with a traverse to solve this problem, we assume that every time to buy is the lowest price to buy, and then calculate every time the lowest price, once found the lowest price is lower than this, we turned to this as the lowest price, but in front of the biggest profits has been saved, not afraid will fall behind ~ this is hanging open!

  2. Did you pass the problem at the first time? What problems did you encounter? What details should you pay attention to?

    My first thought ran out of time…

    class Solution { public int maxProfit(int[] prices) { int[] res = new int[prices.length]; for(int i=0; i<prices.length; i++){ int max = 0; for(int j=i+1; j<prices.length; j++){ if(prices[j] - prices[i] > max){ max = prices[j] - prices[i]; } } res[i] = max; } return Arrays.stream(res).max().getAsInt(); }}Copy the code

  1. There are several solutions, which one has the least time complexity, which one has the least space complexity, and what is the optimal solution? What are other people’s problems? Who’s more efficient? Which language is the fastest to implement in different languages?

I also see the idea of dynamic specification in other people’s solutions:

Iii. AC Code:

class Solution { public int maxProfit(int[] prices) { int min_price = Integer.MAX_VALUE; int max_profit = 0; for(int i=0; i<prices.length; i++){ if(min_price > prices[i]){ min_price = prices[i]; } else if(prices[i] - min_price > max_profit){ max_profit = prices[i] - min_price; } } return max_profit; }}Copy the code

Iv. Summary:

I still have a problem with this topic. I should have thought of dynamic planning at the first time. But it takes a lot of practice to derive the state transition equation.