Topic describes

Method 1: Record the lowest price

Just walk through the price array once, record the all-time low, and on each day consider this question: If I bought at the all-time low, how much money can I make by selling today? When we consider all the days, we have our best answer

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int maxProfit = 0;// Current maximum profit
        for (int i = 0; i < prices.length; i ++) {
            if (prices[i] < min) {
                min = prices[i];// Update the minimum value
            }
            maxProfit = Math.max(maxProfit, prices[i] - min);
        }
        returnmaxProfit; }}Copy the code

Method 2: Dynamic programming

Unoptimized code

class Solution {
    public int maxProfit(int[] prices) {
        int dp[] = new int[prices.length];
        dp[0] = 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            //dp[I] represents the profit made by selling the stock on day I
            dp[i] = Math.max(dp[i - 1].0) + prices[i] - prices[i - 1];
            max = Math.max(max, dp[i]);
        }
        returnmax; }}Copy the code

Optimize the code

class Solution {
    public int maxProfit(int[] prices) {
        int p = 0;
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            // Fuck, write the equation but don't explain it
            p = Math.max(p, 0) + prices[i] - prices[i - 1];
            max = Math.max(max, p);
        }
        returnmax; }}Copy the code