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 stocks
Dynamic programming, double pointer implementation
Review of past dynamic programming
Full backpack 🎒 problem
【 Review old and learn new 】322. Change
Animation demonstration – minimum solution of complete knapsack problem – Implementation of dynamic programming
【 Review old and learn new 】518. Change II
Combinatorial 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 stairs
Full knapsack 🎒 problem AC- Dynamic programming implementation
01 Backpack 🎒 problem
【 Review old and learn new 】474. One and zero
01 knapsack 🎒 problem maximum solution – dynamic programming implementation
【 Review old and learn new 】494. The target and
Expression into 01 knapsack 🎒 problem – dynamic programming implementation
【 Review old and learn new 】1049. The weight of the last stone II
Minimum weight conversion to 01 knapsack 🎒 problem maximum solution – dynamic programming implementation
【 Review old and learn new 】416. Segmentation and subsets
01 knapsack 🎒 problem existence solution – dynamic programming implementation