“This is the 40th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

I. Problem description

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

The best time to buy and sell stocks

Two, the title requirements

Example:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6). Maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

inspection

2. The recommended time is 15 to 30 minutesCopy the code

Third, problem analysis

This is also a typical dynamic programming problem, dynamic programming has not done can see this entry problem solution:

Day 34: Frog jumps step

At first, I wanted to use violence to see if I could pass, but I didn’t expect the data volume of the test to be so large, so direct barbie Q!

After all, it’s dynamic programming, or it’s the old, honest, three-step approach:

Step 1: Understand what it means

They want us to figure out the maximum profit, so dp[I] represents the maximum profit from buying and selling at subscripts 0 to I.

Step 2 Variable initialization:

Dp [0]=0, because it’s the first number, you can’t tell whether to buy or sell.

The third step:

3. I'm sorry. 4Copy the code

The top line represents the array, and the bottom line represents the maximum profit at the current position. What do you think of the above data?

If dp [I] = = prices [I] – prices [I – 1) + dp [I – 1);

Because it’s at least 0, negative numbers need to be 0!

Three steps, call it a day!

Four, coding implementation

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i,j,k,m=0,n=prices.size(a);// Initial information
        int dp[n+2];
        dp[0] =0;// The variable is initialized
        for(i=1; i<n; i++) { k=prices[i]-prices[i- 1];// Rule induction
            dp[i]=k+dp[i- 1];// Rule induction
            if(dp[i]<0)// At least 0
            {
                dp[i]=0;
            }
            m=max(m,dp[i]);// Maximize profit
        }
        return m;// Output the result}};Copy the code

V. Test results