Whenever you’re doing any problem, you want to know what the variables are

The title reads as follows

Given an array, its ith element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Source: LeetCode

The overall logical

Let’s say we havetimesOpportunity at the time, at noendDay can gain the greatest benefitHow should I express it? If it’s in betweenstartCarry out the purchase, then if at noendIf I sell it on the first day, I get the following return

To determine the maximum value, first determine the value of the following expression:

.

All you have to do is go fromto,The maximum value of theta is good.

Detail 1

For each of themNeed to be fromtoAre we sure about the maximum?

The answer is no, because ifThe value is determined, then the value of the following expression is evaluated

The corresponding value is actually the following expression

Compared with, is one more comparative situationTo summarize, this is the following expression

That is, you just need to compare with the previous result again.

Details of the 2

For each of themThe results are all inTo sell the stock for maximum profit?

The answer is no, as can be seen from a simple example. For example, inWhen the stock price is zeroYou should not sell your shares on the third day because you can make more money on the second day.

The overall code

func maxProfit(prices []int) int {
    length := len(prices)
    if length <= 1 {
        return 0
    }
    mark := make([] []int.3)
    for idx := 0; idx < 3; idx++ {
        mark[idx] = make([]int, length)
    }

    for llen := 1; llen < 3; llen++ {
        maxPre := -prices[0]
        for end := 1; end < length; end++ {
          	/ / 1 for details
            if tmpMax := mark[llen- 1][end- 1] - prices[end]; tmpMax > maxPre {
                maxPre = tmpMax
            }
          	2 / / details
            if tmpMax := prices[end] + maxPre; tmpMax > mark[llen][end- 1] {
                mark[llen][end] = tmpMax
            } else {
                mark[llen][end] = mark[llen][end- 1]}}}return mark[2][length - 1]}Copy the code