Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

Suppose the price of a stock is stored in an array in chronological order. What is the maximum profit that can be made by trading the stock at one time?

Example 1:

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 greater than the buying price.

Example 2:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.

Limitations:

0 <= Array length <= 10^5

Their thinking

Violent solution

Pure violence, before buying a stock must be sold, so you can iterate through the array again, found in each cycle before I the smallest element, and then use the current sell price minus before the minimum purchase price to calculate the selling price can get the biggest profits, in update the total profits biggest.

Note: at this time, the time complexity is O(n) because there are two cycles; If the data set is larger, it may not pass.

Dynamic programming solution

State: the dp array is used to store the maximum stock profits for each day, which has the property of the maximum stock on day I

Dp (n) = Max (dp(n-1), prices[n] -min); The comparison between the maximum value of the stock on day I minus 1 and the maximum value of the stock on day I

code

Violent solution

Class Solution {public: int maxProfit(vector<int>& prices) {• int length = prices.size(); • If (length == 0) return 0; • int result = 0; • for(int I = 1; i < length; I ++) • {• int min1 = 1e9; • for(int j = 0; j < i; J ++) • {• if(min1 > prices[j]) min1 = prices[J]; • •} • • result = Max (result,prices[I] -min1); • //cout << result << "<< min1 <<endl; •} • return result; }};Copy the code

Dynamic programming

class Solution { public: const int N = 100010; int maxProfit(vector<int>& prices) { int length = prices.size(); if(length == 0) return 0; int result = 0; int q[N]; Int min = prices[0]; // Prices [0]; for(int i = 1; i < length; i++) { if(min > prices[i]) min = prices[i]; q[i] = max(q[i -1],prices[i] - min); } return q[length - 1]; }};Copy the code