Topic describes

Given an array prices, prices[I] is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3. Example 2:

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can’t buy stocks on day 1 and day 2 and then sell them later. Because you’re doing multiple trades at once, you have to sell your shares before you can buy them again. Example 3:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

Tip:

1 <= prices.length <= 3 * 104 0 <= prices[i] <= 104

Their thinking

Greedy algorithm

  • Single trading day: assuming p1 is added on the same day and p2 is the price on the next day, the profit of selling on the second day is profit= P2-P1 (profit<0, no loss is sold)
  • Consecutive rising trading days: Assume that the consecutive rising trading prices are P1, P2, P3… pn; Buy on the first day and sell on the NTH day; Profit =pn-p1;
    • This situation is equivalent to buying and selling every day; pn-p1=(p2-p1)+(p3-p2)+… (pn-pn-1);
  • Consecutive losing days: do not buy or sell;

Space-time complexity

  • Time complexity O(N) : price is traversed only once;
  • Space complexity O(1) : Variables use constant extra space.

code

function maxProfit(prices: number[]) :number {
    
    let profit:number=0;
    for(let i=1; i<prices.length; i++){let res=prices[i]-prices[i-1];
        if(res>0) {// If there is a profit, sell; Can sell on the day and buy again on the day;
            profit+=res;
        }// 
    }// end of for loop
    return profit
};
Copy the code

Dynamic programming

Dynamic programming trilogy
  • Defining the meaning of DP
    • Define the dp [n] [2] :
    • N means on day NTH there are two states, hold or not hold
    • Dp [I][0] The maximum profit obtained by not holding on day I;
    • Dp [I][1] The maximum profit obtained by holding on day I; (Tip: Hold not buy)
  • Define the state transition equation:
    • dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])

    For today do not hold, can be transferred from two states: 1. Yesterday did not hold; 2. Hold yesterday, sell today. Take the larger value of both.

    • dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);

    For holding today, you can transfer from two states: 1. 2. Don’t hold yesterday, buy today. Take the larger value of both.

  • Initialize the dp.
    • Don’t hold: dp [0] [0] = 0;
    • Hold :dp[0][1]=-prices[0]

Since dp[n][0]> DP [I][1], the profit of not holding stocks on that day must be greater than that of holding stocks on that day, so return DP [LEN-1][0]

Space-time complexity

  • Time complexity: O(n), it can be traversed once.
  • Space complexity: O(n)

code

function maxProfit(prices: number[]) :number {
  // Dynamic programming;
  // define dp[n][2] :
     // dp[I][0]
     // dp[I][1]
  // Define the state transition equation:
      
    // dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])
    // dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]);

   // dp initialization
    // dp[0][0]=0;
    // dp[0][1]=-prices[0]
    let len=prices.length;
    let dp=new Array(len);
    for(let i=0; i<len; i++){ dp[i]=new Array(2).fill(0)
    }
    dp[0] [0] =0;
    dp[0] [1]=-prices[0]

    for(let i=1; i<len; i++){ dp[i][0] =Math.max(dp[i-1] [0],dp[i-1] [1]+prices[i])
      dp[i][1] =Math.max(dp[i-1] [0]-prices[i],dp[i-1] [1]);
    }// end of for loop

    return dp[len-1] [0]};Copy the code

Optimization: during state transition, dp[I] will only be transferred from DP [i-1], so the first dimension can be removed:

Space-time complexity

  • Time complexity: O(n), it can be traversed once.
  • Space complexity: O(1)
function maxProfit(prices: number[]) :number {
  // Dynamic programming;
    let len=prices.length;
    let dp=new Array(2).fill(0);

    dp[0] =0;
    dp[1]=-prices[0]

    for(let i=1; i<len; i++){let temp=dp[0]
      dp[0] =Math.max(dp[0],dp[1]+prices[i])
      dp[1] =Math.max(temp-prices[i],dp[1]);
    }// end of for loop

    return dp[0]};Copy the code

Past stock issues

【 Review old and learn new 】121. The best time to buy and sell stocksDynamic programming, double pointer implementation

Review of past dynamic programming

Full backpack 🎒 problem

【 Review old and learn new 】322. ChangeAnimation demonstration – minimum solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】518. Change IICombinatorial solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】377. Sum of combinations ⅳPermutation solution of complete knapsack problem – Implementation of dynamic programming

【 Review old and learn new 】70. Take the stairsFull knapsack 🎒 problem AC- Dynamic programming implementation

01 Backpack 🎒 problem

【 Review old and learn new 】474. One and zero01 knapsack 🎒 problem maximum solution – dynamic programming implementation

【 Review old and learn new 】494. The target andExpression into 01 knapsack 🎒 problem – dynamic programming implementation

【 Review old and learn new 】1049. The weight of the last stone IIMinimum weight conversion to 01 knapsack 🎒 problem maximum solution – dynamic programming implementation

【 Review old and learn new 】416. Segmentation and subsets01 knapsack 🎒 problem existence solution – dynamic programming implementation