122. The best time to Buy and sell stocks II


Their thinking

Method 1: Brute force search

Brute force search may not satisfy some interviewers, but I think we can start with search algorithms and consider better ones.

There is no limit to the number of trades. On each day, we can choose the corresponding operation based on whether we currently own the stock.


class Solution {
    private int res;
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
 }  int len = prices.length;  this.res = 0;  dfs(prices, 0, len, 0, res);  return this.res;  }  / * ** array of @param prices* @param index the current day, starting from 0* @param status 0 indicates that you do not own shares, and 1 indicates that you own shares* @param profit current profit* / private void dfs(int[] prices, int index, int len, int status, int profit) { // Recursive termination condition if (index == len) {  this.res = Math.max(this.res, profit);  return;  }  dfs(prices, index + 1, len, status, profit);   if (status == 0) { // Try switching to 1 dfs(prices, index + 1, len, 1, profit - prices[index]);  } else { // If status == 1, try 0 dfs(prices, index + 1, len, 0, profit + prices[index]);  }   } } Copy the code

Overtime is expected. Note that this timeout is for large data sizes, so it shows that the search algorithm is correct.

Method 2: Greedy algorithm

The process for using greedy algorithms looks like this:

  • From the firstiHere the day (i >= 1) beginning, with noi - 1If the share price has risen (strictly), the higher the share price will be(prices[i] - prices[i - 1])Total profit, according to this algorithm, the result is the maximum profit that meets the question.

The algorithm is described as follows:

  1. The algorithm can only be used for calculation, butThere’s not a lot of real trading going on, but a greedy algorithm can be used to calculate the maximum profit that the problem asks for. The following illustrates this equivalence[1, 2, 3, 4]For example, the stock price rises in succession over the four days. According to the greedy algorithm, the maximum profit obtained is:
# Java
Res = (prices[3] -prices [2]) + (prices[2] -prices [1]) + (prices[1] -prices [0]);    = (prices[3] - prices[0]);
Copy the code

Looking closely at the formula above, the greedy algorithm suggests that we should buy yesterday and sell today on index 1, 2, and 3, which the title doesn’t allow, but is equivalent to “buy on index 0 and sell on index 3”.

  1. And I want to explain why it’s called the greedy algorithm.

Definition of greedy algorithm:

Algorithms for solving optimization problems usually go through a series of steps, with multiple choices at each step. For many optimization problems. Using dynamic programming algorithms for optimal solutions is a bit of an overkill. Simpler, more efficient algorithms can be used. The Greedy algorithm is one such algorithm. At each step it makes the choice that looks best at the time, that is, it makes the locally optimal choice altogether, hoping that such a choice will lead to the globally optimal solution.

Greedy algorithms always make the best choice in the moment at each step.Copy the code

so

  • “Greedy algorithm” and “dynamic programming”, “backtracking search” algorithm, to complete one thing, is distributed decision;
  • The “greedy algorithm” always makes the best choice at each step, which is understood as “best” :
    • The meaning of “best” often depends on the title, may be “minimum” or “maximum”;
    • Greedy algorithms, compared with dynamic programming, do not look at the front (that is, it does not need to transition from such a state), nor look at the back (there is no aftereffect, the latter choice does not affect the previous choice), so the time complexity of greedy algorithms is generally linear, the space complexity is constant level.
    • The greedy part of this question is that there are three possible results for “today’s stock price – yesterday’s stock price” :(1) integer (2) 0 (3) negative. The greedy algorithm’s decision is to add only integers.
class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int len = prices.length;
        for (int i = 0; i< len - 1; i++) {
 int diff = prices[i + 1] - prices[i];  if(diff > 0) {  res += diff;  }  }  return res;  } } Copy the code

Equivalent writing:

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int len = prices.length;
        for (int i = 0; i< len - 1; i++) {
 int += Math.max(prices[i + 1] - prices[i], 0);  }  return res;  } } Copy the code

Complexity sharing

  • Time complexity:O(N)Here,NRepresents the array length of the stock price.
  • Space complexity:O(1)

Method 3: Dynamic programming

The reason for thinking about dynamic programming is that problems that can be solved by greedy algorithms can generally be solved by dynamic programming. Therefore, we might as well consider from the point of view of “state” and “state transition equation”, and use the idea of dynamic programming to solve this problem.

Ideas:

1. Define the status

The state dp[I][j] is defined as follows:

  • The first dimension:iIndicates that the index isiThat day (It has a prefix property, that is, it takes into account the benefits of the previous days) the maximum profit that can be made;
  • The second dimension,jIndicates that the index isiStock or cash on that day. here0It means you’re holding cash(cash) , 1Holding stock(stock).

2. Think about state transition equations

  • We start with cash, and then on the last day, the state we care about is cash.

  • Each day the state can shift, but also can not understand. State transitions are represented by the following figure:

    (The state transition equation is written in the code)

Description:

  • Since there is no limit to the number of transactions, the status may not change or change from day to day except the last.
  • When you write code, instead of dealing with the last day separately, you can print out the last day with a state of zero0When the value can be.

3. Determine the starting point

At the beginning:

  • If nothing is done,dp[0][0] = 0;
  • If you buy the stock, the current yield is negative, i.edp[0][1] = -prices[i];

4. Confirm termination

When terminated, output dp[len-1][0], because there must be dp[len-1][0] > dp[len-1][1].

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) return 0;

// 0: Hold cash// 1: Hold stock// Status transition: 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> 0 int[][] dp = new int[len][2];  dp[0][0] = 0;  dp[0][1] = -prices[0];   for (int i = 1; i < len; i++) { // The order of the two lines can also be reversed 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 represents the length of the stock price array. Space complexity: O(N), although two digits, but two-dimensional is a constant, independent of the problem size.

You can also set the state array separately to make the semantics more explicit

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
 return 0;  }  // Cash: hold cash// hold the stock// State array// State transition: cash → hold → cash → hold → cash → hold → cash int[] cash = new int[len];  int[] hold = new int[len];   cash[0] = 0;  hold[0] = -prices[0];   for (int i = 1; i < len; i++) { // The order of the two lines can also be reversed cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i]);  hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);  }  return cash[len - 1];  } } Copy the code

5. Consider state compression

Since the current line only refers to the previous line, each line has two values, consider using “scrolling variables” (the “scrolling array” technique).

public class Solution {

    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
 return 0;  }  // Cash: hold cash// hold the stock// State transition: cash → hold → cash → hold → cash → hold → cash  int cash = 0;  int hold = -prices[0];   int preCash = cash;  int preHold = hold;  for (int i = 1; i < len; i++) {  cash = Math.max(preCash, preHold + prices[i]);  hold = Math.max(preHold, preCash - prices[i]);   preCash = cash;  preHold = hold;  }  return cash;  } } Copy the code

Complexity analysis

  • Time complexity: O(N), where N represents the length of the stock price array.
  • Space complexity: O(1), using two rolling variables respectively, to compress the state of a latitude array to a constant.

Some pictures from the network, copyright to the original author, delete.Copy the code