This is a greedy algorithm problem, haven’t done for a long time, have forgotten to solve the problem process. In retrospect, I finally recall the formula of greedy algorithms:

  1. The proof can start with greedy choice

  2. It is proved that the problem is reduced to a similar sub-problem of small scale by using greedy choice

  3. Finally, induction is used to prove that the optimal solution can be produced

You can look at my algorithm summary and see the details of using greedy algorithms.

The best time to buy and sell stocks II

You are given an array prices, where prices[I] represents the price of the stock on day I.

On each day, you may decide to buy and/or sell shares. You can’t hold more than one share at any time. You can also buy it and sell it on the same day. Return the maximum profit you can make.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 7 Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3. Example 2:

Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), this transaction will make a profit = 5-1 = 4. Note that you can’t buy stocks on day 1 and day 2 and then sell them later. Because you’re doing multiple trades at once, you have to sell your shares before you can buy them again. Example 3:

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

Their thinking

The code location is: github.com/shidawuhen/…

To use the greedy method, the main need is to find greedy strategies. My strategy is simple:

  1. You have to have stock, and if you sell it that day, you sell it and then you hold the stock of that day

  2. Whenever there is a profit, make it immediately, regardless of the long term

  3. If you can’t sell it the next day, it means that the stock price is lower the next day, so you change your stock to a lower stock

When these three points are added together, the problem is reduced to smaller, similar sub-problems, and the end result is consistent with the long-term benefits.

code

func maxProfit(prices []int) int {
  sumVal := 0
  if len(prices) == 0 {
    return sumVal
  }
  currentPrice := prices[0]
  for i := 1; i < len(prices); i++ {
    if prices[i]-prices[i- 1] > 0 { / / can be sold
      sumVal += prices[i] - currentPrice
      currentPrice = prices[i] // Pick up where you left off
    } else {
      currentPrice = prices[i] // The description is smaller}}return sumVal
}
Copy the code