当前位置：网站首页>Sword finger offer 63 Maximum profit of stock

Sword finger offer 63 Maximum profit of stock

2022-07-07 22:52:00 【Yes' level training strategy】

subject ： Suppose you store the price of a stock in an array in chronological order , What's the maximum profit you can get from buying and selling this stock at one time ？

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 .

Example 2:

Input : [7,6,4,3,1]

Output : 0

explain : under these circumstances , No deal is done , So the biggest profit is 0.

This topic is relatively simple , Looking for the most profitable , That is to find the cheapest day to buy , Then I bought it on the most expensive day .

The most intuitive violent solution is twice for The cycle can be completed , But the time complexity is O(n^2).

Actually , Just borrow a variable minPrice Record the cheapest price , Then traverse the array once , Subtract the price of the day each time minPrice obtain res , The biggest record res , It is the biggest profit .

class Solution {
    
    public int maxProfit(int[] prices) {
    
      int minPrice = Integer.MAX_VALUE;
      int res = 0;
      for (int i = 0; i < prices.length; i++) {
    
        minPrice = Math.min(minPrice, prices[i]);
        res = Math.max(res, prices[i] - minPrice);
      }
      return res;
    }
}