Topic describes

Given an array prices, prices[I] is the price of a given stock on day I. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible. Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Method one: greed

Their thinking

The stock price of the day is higher than the previous day can be a profit operation, multiple profit operations can be added up to the maximum profit

Code sample

const maxProfit = function(prices) {
    let result = 0;
    let n = prices.length;
    for (let i = 1; i < n; ++i) {
        result += Math.max(0, prices[i] - prices[i - 1]);
    }
    return result;
};
Copy the code

Complexity analysis

Time complexity: O(n), where n is the length of the array. We only need to go through the array once: order 1. You just need constant space for a few variables.

Method two: dynamic programming

Their thinking

At the end of each trading day, there can be only one stock or no stock in hand

  1. Dp [I][0] represents the maximum profit on day I when there is no stock in hand. If there is no stock, there may be no stock on the previous day, or there are stocks on the previous day and they are sold on day I. The formula is as follows:
dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i])
Copy the code
  1. Dp [I][1] represents the maximum profit of holding the stock on day I. Holding the stock may be holding the stock on the previous day, or buying the stock on day I if there is no stock on the previous day. The formula is as follows
dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
Copy the code

Code implementation

const maxProfit = function (prices) {
  const len = prices.length;
  const dp = new Array(len).fill(0).map(v= > new Array(2).fill(0));
  dp[0] [0] = 0;
  dp[0] [1] = -prices[0];
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1] [0], dp[i - 1] [1] + prices[i]);
    dp[i][1] = Math.max(dp[i - 1] [1], dp[i - 1] [0] - prices[i]);
  }
  return dp[len - 1] [0];
};
Copy the code

Complexity analysis

Time complexity: O(n), where n is the length of the array. There are 2N states, and the time complexity of each state transition is O(1). Therefore, the time complexity is O(2n)=O(n) space complexity: O(n). We need O(n) space to store all the states in dynamic programming. If you use spatial optimization, the spatial complexity can be optimized to O(1).

Optimizing spatial complexity

Just focus on what you did today and what you did the day before

const len = prices.length;
  let cash = 0;
  let hold = -prices[0];
  // Maximum profit from holding cash the day before
  let preCash = cash;
  // Maximum profit from holding stocks the previous day
  let preHold = hold;
  for (let i = 1; i < len; i++) {
    // Day I holds the maximum profit in cash
    cash = Math.max(preCash, preHold + prices[i]);
    // Day I maximum profit from holding stock
    hold = Math.max(preHold, preCash - prices[i]);
    // Update the maximum profit held in cash the previous day
    preCash = cash;
    // Update the maximum profit of the stock held the previous day
    preHold = hold;
  }
  return cash;
Copy the code

Space complexity: O(1). We just need a constant variable.