Location>code7788 >text

Linear dp: LeetCode122. best time to buy and sell stocks ll

Popularity：525 ℃/2024-09-10 21:22:05

buy and sell stocks

  • The content of this article is the same as LeetCode 122. The best time to buy and sell stocks ll, which is the same question, so you can challenge yourself after reading this article!
  • Power Button Link

Title Narrative:

Given an array of length N, the ith number in the array represents the price of a given stock on the ith day.

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

Note: You cannot be involved in more than one trade at the same time (you must sell your shares before buying again). A single purchase and sale are combined into a single transaction.

Input Format:

The first line contains the integer N, which represents the number of days. The second line contains N positive integers not greater than 10000 indicating the price of the stock each day.

output format

Outputs an integer representing the maximum profit.

Input Sample 1

6
7 1 5 3 4 6

Sample output 1

7

Input Sample 2

5
7 6 4 3 1

Sample output 2

0

Sample Explanation:

  • Sample 1: Buy on day 2 and sell on day 3, this transaction yields a profit = 5-1 = 4. Then buy on day 4 and sell on day 6, this transaction yields a profit = 6-3 = 3. The total profit is 4+3 = 7.
  • Sample 2: In this case, no trades are made, so the maximum profit is 0.

Dynamic planning ideas explained:

  • We analyze the total profit to see that it is about the number of daysi as a function of day i, and at day i there are only two states corresponding to it
    • 1. No ticket in hand:dp[i][0]
    • 2. Tickets in hand:dp[i][1]
  • So that means we can set thedp[i][0],dp[i][1] for the state variables, and then perform a transfer of states to finally arrive at the answer we need.

1. Meaning of state variables

  • dp[i][0]denoteidays, the maximum profit that can be made when there are no tickets in hand
  • dp[i][1]denoteiDays, the maximum profit that can be made with a ticket in hand

2. Recursive formulas

  • We can use directed graphs with weights to understand this process vividly, and we need to know the recursive formula to understand that process of state transfer, i.e., which previous states our current state is derived from.

      1. dp[i][0]denotes the maximum profit that can be obtained on day i, when there are no tickets in hand.dp[i-1][0] cap (a poem)dp[i-1][1] The first is the first of the two.i-1day, the two states of having a ticket in hand or not having a ticket in hand are derived if the firsti-1days without a ticket in hand, then it means that no transaction has taken place, then thedp[i][0]=dp[i-1][0] and vice versa, fromi-1Days with tickets to the firstidays without tickets, then it means that we sold the stock on day i, when thedp[i][0]=dp[i-1][1]+w[i] , since we are taking the maximum profit, it is said to be the maximum of the two, i.e.:
      dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
      1. dp[i][1] It's also the same thing, in much the same way as the derivation above, so I won't go into it again
      dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);

  • So, the general recursive formula is as follows:

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);

3. How to initialize?

  • How do we initialize the boundary conditions from this recursive formula?
  • Suppose we start on day 1 and end on day n. Then our two states on day 1 are the boundary conditions
dp[1][0]=0; //Maximum profit with no ticket on day 1 is 0
dp[1][1]=-w[1]; //Ticket on day 1 proves I bought that stock on day 1

4. Traversal order

  • From the recurrence formula, our state variabledp[i][0],dp[i][1]depend ondp[i-1][0],dp[i-1][1] . So let's say that we traverse in the order that we traverse from front to back.

5. Example of printing a dp array

  • In this question, the reader can verify the correctness of our dp array by inserting a printf statement inside the for loop.

Code:

#include<iostream>
#include<cstring>
using namespace std.
Const int N = 100010; int w[N],dp[N][2];
int w[N],dp[N][2]; int n; int
int n;

int main(){
  scanf("%d", &n);
  for(int i=1;i<=n;i++) scanf("%d", &w[i]);

  dp[1][0]=0; dp[1][1]=-w[1];
  for(int i=2; i<=n; ++i){
    dp[i][0]=max(dp[i-1][0],dp[i-1][1]+w[i]);
    dp[i][1]=max(dp[i-1][1],dp[i-1][0]-w[i]);
  }
    // On day n, no ticket in hand must be the most profitable, so that means there's no need to take the maximum of both.
  cout<<dp[n][0];
}

Reference Code for LeetCode122

class Solution {
public.
int maxProfit(vector<int> & prices) {
vector<vector<int> > dp((),vector<int>(2));
        // Perform the initialization condition
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < (); i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[() - 1][0];
}
}.
<Previous