Maximum profit of stock (offer 63)

The biggest profit of stocks ( The finger of the sword Offer 63)

1 Title Description

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 ？

 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 .

2 Thought analysis

Using the violence method, the first layer cycle points to the day of purchase , The time complexity of finding the most profitable transaction every day after the second layer loop traverses is O(n²)：

Co ownership n God , The first a Tianmai , The first b Days to sell , We need to ensure that a < b; Total number of transaction schemes available (n-1)+(n-2)+···+2+1=(n-1)n/2.

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int len = prices.length;
        int res = 0;
        int max = 0;
        for(int i = 0;i<len;i++){
    
            for(int j = i+1;j<len;j++){
    
                res = prices[j]-prices[i];
                max = Math.max(res,max);
            }
        }
        return max;
    }
}

Time complexity is too high , Consider using dynamic programming to reduce time complexity .

State definition : set up dp Array dp[i] To i The maximum profit of all feasible transactions within days , The former i Maximum profit per day .

Transfer equation : Before the analysis i The maximum profit per day is the former i-1 Day maximum profit and day i Day selling profit whichever is greater .
$$dp[i]=max\{dp[i-1],prices[i]-min(prices[1:i)]\}$$

$$frontiJapanmostBigbenefitMoisten=max(front(i-1)JapanmostBigbenefitMoisten,The\; firstiJapanpricegrid-frontiJapanmostlowpricegrid)$$

Among them, before getting i The time complexity of the daily lowest price is O(i); You can use a variable to save when traversing the array .

Reduce the time complexity again O(i) To O(1), That is, the transfer equation can be obtained by traversing the array once ：
$$dp[i]=max\{dp[i-1],prices[i]-min(minPrice,peices[i])\}$$
Reduce space complexity ： Because only find dp Maximum of , So you can use a variable instead of dp Array
$$profit=max(profit,prices[i]-min(minPrices,prices[i]))$$
Finally, the time complexity is O(n), The space complexity is O(1)

class Solution {
    
    public int maxProfit(int[] prices) {
    
        if(prices.length==0){
    
            return 0 ;
        }
        int len = prices.length;
        int res = prices[0];
        int max = 0;
        for(int i = 1;i<len;i++){
    
            // Before recording i Daily minimum 
           if(res>=prices[i]){
    
               res = prices[i];
           }
            // Update maximum profit 
           max = Math.max(max,prices[i]-res);
        }
        return max;
    }
}

3 Buckle address

https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58vmds/