[Jianzhi offer] 63 Maximum profit of stock

The finger of the sword Offer 63. The biggest profit of stocks

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 ？

Ideas

• dp[i] Representative to prices[i] Maximum profit for the ending subarray
• State transition equation ： front i Maximum daily profit = max( front (i - 1) Maximum daily profit , The first i Daily price - front i Daily minimum price )

Code

class Solution {
    
    public int maxProfit(int[] prices) {
    
        int cost = Integer.MAX_VALUE,profit = 0;

        for(int price:prices){
    
            cost = Math.min(cost,price);//  Find the lowest price in history 
            profit = Math.max(profit,price - cost);//  Update maximum profit 
        }
        return profit;
    }
}