Leetcode notes 121. the best time to buy and sell stocks

Title Description

Topic linking

Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

Example 1：

Input ：[7,1,5,3,6,4]
Output ：5
explain ： In the 2 God （ Stock price = 1） Buy when , In the 5 God （ Stock price = 6） Sell when , Maximum profit = 6-1 = 5 .
Note that profit cannot be 7-1 = 6, Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .
Example 2：

Input ：prices = [7,6,4,3,1]
Output ：0
explain ： under these circumstances , No deal is done , So the biggest profit is 0.

Tips ：

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁴

Ideas

The first thought of violent solution , It goes without saying , Is to calculate all possible situations , The advantage of this method is that it takes less memory , After all, you don't need to save anything , But its time complexity is $\mathcal{O}(n^2)$, This is unacceptable .

The second way of thinking , Through analysis , The essence of maximum benefit , yes $argmax\{maxcos{t}_i-mincos{t}_i\}$, namely The first 1 ~ N The maximum cost in a day - The first 1~i The minimum cost in a day , And these two values , It only takes one time to solve , So the time complexity of this method is $\mathcal{O}(n)$ That's good .

Code

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int maxp[100005] {
    };
        int minp[100005] {
    };
        minp[0] = prices[0];
        maxp[prices.size() - 1] = prices[prices.size() - 1];
        int ans = 0;
        for(int i = 1; i < prices.size(); ++i)
        {
    
            minp[i] = min(minp[i - 1], prices[i]);
        }
        ans = max(0, maxp[prices.size() - 1] - minp[prices.size() - 1]);
        for(int j = prices.size() - 2; j >= 0; -- j)
        {
    
            maxp[j] = max(maxp[j + 1], prices[j]);
            ans = max(ans, maxp[j] - minp[j]);
        }
        return ans;
    }
};