Offer:[day 8 dynamic planning (simple)] --- > maximum profit of stock

---

One 、 Title Description

Suppose you store the price of a stock in an array in chronological order , What's the maximum profit you can get from buying and selling this stock at one time ？

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 .

Example 2：

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

Limit ：
0<= The length of the array <=10^5

Two 、 Thought analysis

notes ： Some contents and pictures in the train of thought analysis refer to the solutions of your predecessors , Thank them for their selfless dedication

Dynamic programming ---- Conventional methods

front i Maximum daily profit dp[i] Equal to before i-1 Maximum daily profit dp[i-1] And the i The maximum of the maximum profit sold on the day .
front i Maximum daily profit = max( front ($i-1$) Maximum daily profit , The first $i$ Daily price $-$ front $i$ Daily minimum price )
$\mathrm{d}\mathrm{p}[\mathrm{i}]=\mathrm{m}\mathrm{a}\mathrm{x}(\mathrm{d}\mathrm{p}[\mathrm{i}-1],\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}[\mathrm{i}]-\mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}[0:\mathrm{i}]))$

Efficiency optimization ：
① Reduced time complexity ： front i The lowest price per day $\mathrm{m}\mathrm{i}\mathrm{n}(\mathrm{p}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}[0:\mathrm{i}])$ The time complexity is O(i). And traversing prices when , With the help of a variable ( Recorded as cost cost) Update the minimum price every day .
② Reduced space complexity ： because dp[i] Only with dp[i-1]、prices[i]、cost relevant , So you can use a variable ( Recorded as profit profit) Update the maximum profit every day .








Complexity analysis ：
Time complexity $\mathrm{O}(\mathrm{N})$： among N by prices List length , Dynamic planning needs to traverse prices
Spatial complexity $\mathrm{O}(1)$： Variable cost and profit Use extra space of constant size .

Dynamic programming ---- Online processing

Algorithm flow ：
① Define two variables max and tmp, Represents maximum profit and current profit
② Traversing an array , The current profit is accumulated at each cycle ,tmp+=rices[i]-prices[i-1]
③ If current profits tmp Greater than the maximum profit max, Then update the maximum profit max Value .
③ If tmp Less than or equal to max, also tmp Less than 0, So it means that no matter what number is added later, it will only make the sum smaller and smaller , We might as well start from scratch , therefore tmp Set as 0.
Complexity analysis ：
Time complexity $\mathrm{O}(\mathrm{N})$： among N by prices List length , Dynamic planning needs to traverse prices
Spatial complexity $\mathrm{O}(1)$： Variable tmp and max Use extra space of constant size .

3、 ... and 、 The overall code

The overall code of the conventional method of dynamic planning is as follows

int maxProfit(int* prices, int pricesSize){
    
    int cost = 1e9;
    int profit = 0;
    for(int i = 0; i < pricesSize; i++){
    
        cost = cost <= prices[i]? cost : prices[i];
        profit = profit >= (prices[i]-cost)? profit : (prices[i]-cost);
    }
    return profit;
}

function , The test passed

The overall code of the dynamic planning online processing method is as follows

int maxProfit(int* prices, int pricesSize){
    
    int max = 0;
    int tmp = 0;
    for(int i = 1; i < pricesSize; i++){
    
        tmp += prices[i]-prices[i-1];
        if(tmp > max){
    
            max = tmp;
        }
        else if(tmp < 0){
    
            tmp = 0;
        }
    }
    return max;
}

function , The test passed