This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

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.Copy the code
  • Example 2:
Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code
  • Limitations:
0 <= Array length <= 10^5Copy the code

Implementation approach

  • Double cycle violence

Double-loop traversal is well understood and can be used to calculate the maximum profit of stock trading in a straightforward manner, but the time complexity requires O(n2).

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let maxprofit = 0;
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            const profit = prices[j] - prices[i];
            if(profit > maxprofit) { maxprofit = profit; }}}return maxprofit;
};
Copy the code
  • Greedy algorithm

The traversal completes and returns the maximum profit of the stock by iterating through each day updating the minimum value of the stock and reaching the maximum profit of the stock for a single day.

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let maxprofit = 0;
    let min = prices[0]
    for (let item of prices) {
        maxprofit = Math.max(maxprofit, item - min)
        if (item < min) {
            min = item
        }
    }
    return maxprofit
};
Copy the code
  • Dynamic programming

Since there are only two operations of holding and not holding on the day of stock trading, let’s define a two-dimensional array, where DP [I][0] represents the maximum profit of holding stocks at the end of the I +1 day (I starts from 0), and DP [I][1] represents the maximum profit of not holding stocks at the end of the I +1 day.

Day 1 yield: -prices[0] if you own stocks, 0 if you don’t.

Day I earnings: if you hold the previous day, you will have a larger profit compared to the previous day. If you do not hold, you will have a larger profit compared to the previous day when you sell stocks.

So each day is the optimal hold and no-hold return, and we get the no-hold return on the last day is the answer to the problem.

/ * * *@param {number[]} prices
 * @return {number}* /
const maxProfit = prices= > {
    const len = prices.length;
    if (len < 2) return 0
    // Create the dp array
    const dp = new Array(len).fill([0.0]);
    // dp array initialization
    dp[0] = [-prices[0].0];
    for (let i = 1; i < len; i++) {
        / / update the dp [I]
        dp[i] = [
            Math.max(dp[i - 1] [0], -prices[i]),
            Math.max(dp[i - 1] [1], prices[i] + dp[i - 1] [0]]), }return dp[len - 1] [1];
};
Copy the code