Fall mother to deny? An air mass out of 6 stock algorithms to pump

Viewing degree: 🌟

Palate: Tiger skin and chicken feet

Cooking time: 10min

I want to clear my stock and go home, but I fear that I may soon rebound and be overwhelmed. Instead of saving negative interest, it is better to muddle between, less chase up, do not kill down, sleep at night, should not hate, profit always in the unintentional. The month has rain or shine round lack, the stock has a horizontal rise and fall, the matter is difficult to complete. — Famous ancients traded for nothing

This article has been included in the front-end canteen warehouse of the same name, Github github.com/Geekhyt. Welcome to the canteen. If you think the food and wine are delicious, it is a great encouragement for the canteen owner to award a STAR.

The fund market has started 2021 with booms and busts. Just meet the god of wealth, looking forward to the young people, just entered the hard to eat a hammer of the capital market.

All kinds of “great appreciation of human delusion” are staged in turn, making the magical world even more magical. If you’ve been down lately, please give us a thumbs-up and let’s stick together for warmth.

Going back to Leetcode’s six-question stock series, these six questions can be grouped into one question:

The best time to buy or sell stocks
The best time to buy or sell stocks II
The best time to buy or sell stocks III
The best time to buy or sell stocks
Best time to buy and sell stocks including frozen period
The best time to buy and sell stocks includes fees

Different from the reality, some restrictions have been added in the question, which is not difficult to find after reading the analysis.

The first one only trades once, so k is equal to 1.
Problem two, we don’t limit the number of trades, so k is equal to plus infinity.
Problem number three only trades twice, so k is equal to 2.
The fourth constraint is that k is an arbitrary number of transactions.
Questions 5 and 6 are open-ended, which are equivalent to adding transactions to the second questionFrozen periodandpoundageAdditional conditions for.

There are three things we can do every day:

buy
sell
No operation

But there are four caveats.

Buy before you sell.
They say you can’t make multiple trades at the same time, which means you have to sell your shares before you can buy them again.
No operation is based on two states, stock in hand and no stock in hand.
There is also a limit on the number of trades k. You can buy only when k BBB 0 = 0.

With these states analyzed, the next step is to translate them into code.

First, we can create a three-dimensional array to represent each of these states, but let’s clarify what the variables mean.

I: Days range is (0 <= I <= n-1)
K: Maximum number of transactions
0: No stock holdings
1: Own stocks
N: The length of the stock array

Dp [I] [k] [0] dp [I] [k] [1] / / an 🌰 dp [2] [2] [1] / / today is the second day, hold shares, also can be at most 2 transactions

The maximum return we finally require is dp[n-1][k][0], which represents the maximum return after selling the stock on the last day. (Here it must be more profitable to sell than to hold, so it is [0], not [1].)

Next, we try to set up the state transition equation.

// If you don't have any stock in your hand today, there are two possibilities: // 1. If you didn't hold any stock yesterday, you can choose not to operate today. Dp [i-1][k][0] dp[i-1][k][0] // 2. Corresponding: Dp [I - 1] [k] [1] + prices [I] dp [I] [k] [0] = math.h Max (dp [I - 1] [k] [0], dp [k] [I - 1] [1] + prices [I]) / / hold the stock today, there are two possible: / / 1. Yesterday in the hands of the stock, today choose not to operate. Dp [i-1][k][1] // 2. I didn't hold the stock yesterday, I bought it today. Corresponding: dp [I - 1] [0] - [k - 1] prices [I] dp [I] [k] [1] = math.h Max (dp [I - 1] [1], [k] dp [I - 1] [0] - [k - 1] prices [I])

Obviously, the profit from selling the stock goes up and the profit from buying the stock goes down. Because each trade consists of two pairs of actions, buy and sell.

Therefore, the maximum profit is the maximum of the two possibilities above, only when the purchase is required to put k minus 1.

Problem one, k is equal to 1

Set the state transition equation into the condition of this problem, k = 1, list the state transition equation.

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]) dp[i][1][1] = Math.max(dp[i - 1][1][1], Dp [I - 1] [0] [0] - prices [I]) = Math. Max (dp [I - 1] [1] [1], - prices [I]) / / k = 0, dp [I - 1] [0] [0] = 0

We see that since k is 1 and doesn’t change, that means that k has no effect on the state transition, we can simplify the equation further.

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

For day 0, we need to initialize:

Don’t hold:dp[0][0] = 0
Hold:Dp [0][1] = -prices[0] dp[0][1] = -prices[0]

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; 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], -prices[i])
    }
    return dp[n - 1][0]
}

Time complexity: O(n)
Space complexity: O(n)

We find that dp[I] will only be transferred from dp[I – 1] during the transfer, so the first dimension can be removed and the space complexity is optimized to O(1).

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], -prices[i])
    }
    return dp[0]
}

Time complexity: O(n)
Space complexity: O(1)

We can also make the variable names a little more friendly.

PROFIT_OUT: Profit when sold
Profit_in: Profit at the time of purchase

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

Time complexity: O(n)
Space complexity: O(1)

Problem two, k is equal to plus infinity

We’re going to put the state transition equation into this problem. K is equal to plus infinity.

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

We find that k in the array has also not changed, that is to say, k has no effect on the state transition, and the equation can be further simplified.

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])

For day 0, we will give an initial value:

Don’t hold:dp[0][0] = 0
Hold:Dp [0][1] = -prices[0] dp[0][1] = -prices[0]

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0 
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; 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[n - 1][0]
}

At the same time, dp[I] will only be transferred from dp[I – 1], so the first dimension can be removed and the space complexity is optimized to O(1).

const maxProfit = function(prices) { let n = prices.length let dp = Array.from(new Array(n), () => new Array(2)) dp[0] = 0 dp[1] = -prices[0] for (let i = 1; i < n; I++) {let TMP = dp[0]; Math. Max (dp[0], dp[1] + prices[I]) dp[1] = Math. Max (dp[1], tmp-prices [I])} return dp[0]}

As in the previous problem, we can make the variable names a little bit more friendly.

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

Problem number three, k is equal to 2

In the first two cases, whether it’s k equals 1, or k equals plus infinity, k has no effect on the state transition equation.

But when k is equal to 2, k has an effect on the state transition equation. List the state transition equation:

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

Now k can’t be simplified, so we have to exhaust k using two cycles.

for (let i = 0; i < n; i++) {
    for (let k = maxK; k >= 1; k--) {
        dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
        dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
}

But because the range of values for k is small, we can just list them all.

dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])

With the above two problems in mind, let’s just write down the dimension-reduction solution for the next few problems.

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {
        dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

As above, we can make the variable names a little more friendly.

const maxProfit = function(prices) {
    let profit_1_in = -prices[0], profit_1_out = 0
    let profit_2_in = -prices[0], profit_2_out = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {
        profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
        profit_1_in = Math.max(profit_1_in, -prices[i])
    }
    return profit_2_out
}

Problem number four, k is any number

A profitable trade takes at least two days (buy the day before, sell the day after, if the purchase price is below the sale price).

If the length of the stock price array is n, then the number of profitable trades is at most n / 2 (integer division). So the threshold for k is n over 2.

If given k is not less than the critical value, that is, k >= n / 2, then k can be extended to plus infinity, as in the case of problem 2, with the following function maxProfit2.

const maxProfit = function(k, prices) { let n = prices.length const maxProfit2 = function(prices) { let profit_out = 0 let profit_in = -prices[0] for (let i = 1; i < n; i++) { profit_out = Math.max(profit_out, profit_in + prices[i]) profit_in = Math.max(profit_in, profit_out - prices[i]) } return profit_out } if (k > n / 2) { return maxProfit2(prices) } let profit = new Array(k) // For (let j = 0; let j = 0; let j = 0; let j = 0; let j = 0; j <= k; j++) { profit[j] = { profit_in: -prices[0], profit_out: 0 } } for (let i = 0; i < n; i++) { for (let j = 1; j <= k; j++) { profit[j] = { profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i]) } } } return profit[k].profit_out }

Problem number five, k is positive infinity but it has a cooling time

Every time you sell, you have to wait a day before you can trade again, so when you choose to buy on day I, you have to move from the I-2 state.

List the state transition equation.

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])

K also has no effect on the state transition, so we can simplify this equation further.

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 - 2][0] - prices[i])

const maxProfit = function(prices) { let n = prices.length let dp_i0 = 0 let dp_i1 = -prices[0]; Let dp_pre = 0 // dp[I -2][0] for (I = 0; i < n; i++) { let tmp = dp_i0 dp_i0 = Math.max(dp_i0, dp_i1 + prices[i]) dp_i1 = Math.max(dp_i1, dp_pre - prices[i]) dp_pre = tmp } return dp_i0 }

As above, we can make the variable names a little more friendly.

const maxProfit = function(prices) {
    let n = prices.length
    let profit_in = -prices[0]
    let profit_out = 0
    let profit_freeze = 0
    for (let i = 1; i < n; i++) {
        let temp = profit_out
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_freeze - prices[i])
        profit_freeze = temp
    }
    return profit_out
}

Problem six, k is positive infinity but there’s a commission

On the basis of the second question, added the handling fee.

Each transaction requires a fee, which can be subtracted from the profit. There are two equations.

The first equation: deduct the handling fee each time you buy a stock

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)

The second equation: deduct the handling fee each time you sell the stock

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices, fee) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {
        let tmp = dp[0]
        dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

As above, we can make the variable names a little more friendly.

const maxProfit = function(prices, fee) {
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

Group out after the stock series algorithm to a beginning and end echo, talk about the so-called investment clock.

Economies are divided into two big cycles: recoveries and recessions. The combination of inflation and liquidity can be divided into four mini-cycles: pre-recession, post-recession, pre-recovery and post-recovery.

Different economic cycles correspond to different asset and market styles. All assets are cyclical, and there is no asset that only goes up and down. Even the core consumption asset like Maotai can be adjusted back by more than 30% on average in an inappropriate cycle, and even the sunset industry like steel can rise by 50% in an appropriate cycle.

Figure out the current is located in which cycle, adjust the reasonable allocation of assets, in order not to do leeks.

Stand on the shoulders of giants

General Solutions to Stock Problems
Simple DP, second understanding of stock trading
The best time to buy or sell stocks

Group Brush Plan of 2021

Front – end canteen LeetCode problem solution warehouse

A flag was set up at the beginning of this year. The warehouse on it will be filled with 100 high-frequency front-end interview questions in 2021, and 50% of the progress has been completed.

If you’re going to do LeetCode, or are doing LeetCode, join the front-end canteen and work together for a good time.

❤️ Love triple hit

1. If you think the food and drinks in the canteen are still appetizing, please click “like” to support it. Your “like” is my biggest motivation.

2. Pay attention to the canteen at the front of the official account and eat every meal well!

3. Thumb up, comments, forwarding === urge more!

Fall mother to deny? An air mass out of 6 stock algorithms to pump

Problem one, k is equal to 1

Problem two, k is equal to plus infinity

Problem number three, k is equal to 2

Problem number four, k is any number

Problem number five, k is positive infinity but it has a cooling time

Problem six, k is positive infinity but there’s a commission

Stand on the shoulders of giants

Group Brush Plan of 2021

❤️ Love triple hit

Related Posts

SolidJS: I React more than React

A Brief Introduction to Active Objects (AO) in JavaScript

Manually implement the simplest version of Promise