Question

122. Best Time to Buy and Sell Stock II

中文文档

Description

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return _the maximum profit you can achieve_.

 

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

Solutions

Solution 1: Greedy Algorithm

Starting from the second day, if the stock price is higher than the previous day, buy on the previous day and sell on the current day to make a profit. If the stock price is lower than the previous day, do not buy or sell. In other words, buy and sell on all rising trading days, and do not trade on all falling trading days. The final profit will be the maximum.

The time complexity is $O(n)$, where $n$ is the length of the prices array. The space complexity is $O(1)$.

class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    return sum(max(0, b - a) for a, b in pairwise(prices))

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

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int ans = 0;
    for (int i = 1; i < prices.size(); ++i) ans += max(0, prices[i] - prices[i - 1]);
    return ans;
  }
};

func maxProfit(prices []int) (ans int) {
  for i, v := range prices[1:] {
    t := v - prices[i]
    if t > 0 {
      ans += t
    }
  }
  return
}

function maxProfit(prices: number[]): number {
  let ans = 0;
  for (let i = 1; i < prices.length; i++) {
    ans += Math.max(0, prices[i] - prices[i - 1]);
  }
  return ans;
}

impl Solution {
  pub fn max_profit(prices: Vec<i32>) -> i32 {
    let mut res = 0;
    for i in 1..prices.len() {
      res += (0).max(prices[i] - prices[i - 1]);
    }
    res
  }
}

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let ans = 0;
  for (let i = 1; i < prices.length; i++) {
    ans += Math.max(0, prices[i] - prices[i - 1]);
  }
  return ans;
};

public class Solution {
  public int MaxProfit(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.Length; ++i) {
      ans += Math.Max(0, prices[i] - prices[i - 1]);
    }
    return ans;
  }
}

Solution 2: Dynamic Programming

We define $f[i][j]$ as the maximum profit after trading on the $i$th day, where $j$ indicates whether we currently hold the stock. When holding the stock, $j=0$, and when not holding the stock, $j=1$. The initial state is $f[0][0]=-prices[0]$, and all other states are $0$.

If we currently hold the stock, it may be that we held the stock the day before and do nothing today, i.e., $f[i][0]=f[i-1][0]$. Or it may be that we did not hold the stock the day before and bought the stock today, i.e., $f[i][0]=f[i-1][1]-prices[i]$.

If we currently do not hold the stock, it may be that we did not hold the stock the day before and do nothing today, i.e., $f[i][1]=f[i-1][1]$. Or it may be that we held the stock the day before and sold the stock today, i.e., $f[i][1]=f[i-1][0]+prices[i]$.

Therefore, we can write the state transition equation as:

$$ \begin{cases} f[i][0]=\max(f[i-1][0],f[i-1][1]-prices[i])\ f[i][1]=\max(f[i-1][1],f[i-1][0]+prices[i]) \end{cases} $$

The final answer is $f[n-1][1]$, where $n$ is the length of the prices array.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the prices array.

class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    n = len(prices)
    f = [[0] * 2 for _ in range(n)]
    f[0][0] = -prices[0]
    for i in range(1, n):
      f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i])
      f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i])
    return f[n - 1][1]

class Solution {
  public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] f = new int[n][2];
    f[0][0] = -prices[0];
    for (int i = 1; i < n; ++i) {
      f[i][0] = Math.max(f[i - 1][0], f[i - 1][1] - prices[i]);
      f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] + prices[i]);
    }
    return f[n - 1][1];
  }
}

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int f[n][2];
    f[0][0] = -prices[0];
    f[0][1] = 0;
    for (int i = 1; i < n; ++i) {
      f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);
      f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);
    }
    return f[n - 1][1];
  }
};

func maxProfit(prices []int) int {
  n := len(prices)
  f := make([][2]int, n)
  f[0][0] = -prices[0]
  for i := 1; i < n; i++ {
    f[i][0] = max(f[i-1][0], f[i-1][1]-prices[i])
    f[i][1] = max(f[i-1][1], f[i-1][0]+prices[i])
  }
  return f[n-1][1]
}

public class Solution {
  public int MaxProfit(int[] prices) {
    int f1 = -prices[0], f2 = 0;
    for (int i = 1; i < prices.Length; ++i)
    {
      f1 = Math.Max(f1, f2 - prices[i]);
      f2 = Math.Max(f2, f1 + prices[i]);
    }
    return f2;
  }
}

Solution 3: Dynamic Programming (Space Optimization)

We can find that in Solution 2, the state of the $i$th day is only related to the state of the $i-1$th day. Therefore, we can use only two variables to maintain the state of the $i-1$th day, thereby optimizing the space complexity to $O(1)$.

The time complexity is $O(n)$, where $n$ is the length of the prices array. The space complexity is $O(1)$.

class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    n = len(prices)
    f = [-prices[0], 0]
    for i in range(1, n):
      g = [0] * 2
      g[0] = max(f[0], f[1] - prices[i])
      g[1] = max(f[1], f[0] + prices[i])
      f = g
    return f[1]

class Solution {
  public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] f = new int[] {-prices[0], 0};
    for (int i = 1; i < n; ++i) {
      int[] g = new int[2];
      g[0] = Math.max(f[0], f[1] - prices[i]);
      g[1] = Math.max(f[1], f[0] + prices[i]);
      f = g;
    }
    return f[1];
  }
}

class Solution {
public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int f[2] = {-prices[0], 0};
    for (int i = 1; i < n; ++i) {
      int g[2];
      g[0] = max(f[0], f[1] - prices[i]);
      g[1] = max(f[1], f[0] + prices[i]);
      f[0] = g[0], f[1] = g[1];
    }
    return f[1];
  }
};

func maxProfit(prices []int) int {
  n := len(prices)
  f := [2]int{-prices[0], 0}
  for i := 1; i < n; i++ {
    g := [2]int{}
    g[0] = max(f[0], f[1]-prices[i])
    g[1] = max(f[1], f[0]+prices[i])
    f = g
  }
  return f[1]
}