# Maximize your profit in the trade market as a developer

# Introduction

Recently, the cryptocurrency market is very interesting. We enjoy making profits from it. But, how can we maximize the profit?

As a developer, I believe there have some algorithms that can pull this job. And I find it in my notebook of a college course, which, of course, I’ve already forgotten how it works :).

It’s time to pick it up. The algorithm that **seeks the optimal solution** is *Dynamic Programming*.

**Dynamic Programming**

The best way to find the optimal solution is to **backtrack** the path of getting this solution.

Suppose that the best solution is `f(n)`

, we need to know how to get to `f(n)`

, which means to find out the equation.

`f(n) = g[f(n-1)]`

If `f(n)`

is the best solution of `nth`

step, then `g[f(n-1)]`

is the **move** from the best solution of `(n-1)th`

step to `nth`

step.

In brief, Dynamic Programming can chunk up an optimal problem into multiply optimal sub-problems.

You may ask, the normal backtracking algorithm can do that, too. What makes Dynamic Programming special? Dynamic Programming **caches the sub-optimal solution**.

The normal backtracking algorithm doesn’t cache the sub-optimal solution, it wastes a lot of time on recalculation. However, Dynamic Programming learns from history. When it meets `f(i)`

, it will use `f(i)`

in the cache.

To sum up, Dynamic Programming is an algorithm that **seeks the optimal** **solution**. The optimal solution must be got from** optimal sub-solutions** in the** past, not the future**. And it can memorize the **optimal sub-solutions **and use them in the current solution.

Enough theory, let’s maximize the profit!

**Problem**

You are given an integer array `prices`

where `prices[i]`

is the price of a given stock on the `ith`

day, and an integer `k`

. Find the maximum profit you can achieve. You may complete, at most, `k`

transactions. You must sell the stock before you buy again. (https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)

The optimal solution is, on the last day, we have the max profit.

First, let’s see what influences the profit.

- Number of transaction: It’s limited by
`k`

- State of buying or selling: when you buy or sell a share, the profit will change
- Price of day

With this information, we can initialize the cache.

`profit = [{"sell": 0, "buy": -prices[0]} for _ in range(k + 1)]`

We can the states of transactions, from 0 transactions to `k`

transactions. Each transaction has 2 profits, profit when selling a share or buying a share. profit of selling is initialized by 0. The profit of buying is initialized by `-prices[0]`

.

We can make `k`

transactions every day. Suppose that we are doing the `ith`

transaction.

The max profit when we are going to **sell** a share is the **max value** of **holding the share **or** selling it at the day price. **The profit of selling it is the sum of the profit of **buying a share of the current transaction **and the day price.

`profit[i]["sell"] = max(`

profit[i]["sell"],

profit[i]["buy"] + prices[day])

The max profit when we are going to **buy** a share is the **max value** of **holding the share **or** buying it at the day price. **The profit of buying it is the sum of the profit of **selling a share of the previous transaction **and the day price.

`profit[i]["buy"] = max(`

profit[i]["buy"],

profit[i - 1]["sell"] - prices[day],)

The key point is to distinguish the current transaction and the previous transaction when we buy or sell a share.

Finally, the max profit is the max value of selling a share.

`return max([trans["sell"] for trans in profit])`

Here is the full script.

# Another way

Previously, we cache the profits by transactions. We can cache them by days, too.

`profit = [[0 for _ in range(days)] for _ in range(3)]`

We initialize the profits of each day are 0. We need to add another dimension to track the transaction. There are 3 states of transaction: no transaction, previous transaction, and current transaction.

However, using this initialization, we lose the track of the profit of selling or buying a share. So, we set `profit`

for the profits of selling. We use a variable to keep the max profit of buying for each transaction.

This method **uses less space** to cache the profits. However, it’s more difficult to write and understand. Because it not only uses an array but also a variable to cache the profits.

Both two transactions apply the notion of the current transaction and the previous one, which, again, it’s the key point of the solution.

**Conclusion**

Dynamic Programming can seek the optimal solution. Back to the topic, How can we make more money using it? We need to know the limit of the number of transactions, track the profit when we sell or buy a share, and have the price of the share every day.

Oh no. The last condition is a little bit difficult. It seems that we need a time machine to go to the future, get the prices, come back and make the decision.

OK, That’s fine. Now we just need to build a time machine.