Leetcode 121 best time to buy and sell stock (simple)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock

Given an array  prices , It's the first  i  Elements  prices[i]  Represents the number of shares in a given stock  i  Sky price .

You can only choose   One day   Buy this stock , And choose   A different day in the future   Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return  0 .

Example  1：

Input ：[7,1,5,3,6,4] Output ：5 explain ： In the  2  God （ Stock price  = 1） Buy when , In the  5  God （ Stock price  = 6） Sell when , Maximum profit  = 6-1 = 5 . Note that profit cannot be  7-1 = 6,  Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .

Example  2：

Input ：prices = [7,6,4,3,1] Output ：0 explain ： under these circumstances ,  No deal is done ,  So the biggest profit is  0.

Tips ：

• 1 <= prices.length <= 105

• 0 <= prices[i] <= 104

Two 、 Their thinking

Traversing the array once , In every position i when , Record i The lowest of all prices before the location , Then take the current price as the selling price , Check whether the current revenue is the maximum revenue .

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int maxProfit(int[] prices) {
 //  Record i The lowest of all prices before the location
 int buy = prices[0];
 //  The biggest profit at the moment
 int profit = 0;
 for (int i = 1; i < prices.length; i++) {
 buy = Math.min(buy, prices[i]);
 profit = Math.max(profit, prices[i] - buy);
 }
 return profit;
 }
}


Four 、 Summary notes

• 2022/7/3  It will rain for the next few days