# Max Profit With K Transactions

# Max profit with k transactions

`project_name = "max-profit-with-k-transactions"`

### Problem Statement

You are given an array which contains integers repressenting the `prices`

of a stock during a certain day. The index of the array represents the day in which the stock was valued at that price.

For example given the array `prices`

= [3, 8, 1]:

```
on day 0 (prices[0]) the price of the stock was 3
on day 1 (prices[1]) the price of the stock was 8
on day 2 (prices[2]) the price of the stock was 1
```

If you are allowed to make at most `k`

numbers of transactions, find the maximum profit you can achieve.

```
-You can only engage in one transaction at a time, if you bought then you must sell before buying again.
-You must buy before you sell (obviously) so you cant buy on day two and sell on day one for instance.
```

Here is an example of how to achieve this:

```
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
```

Source: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

### The Method

Here's the systematic strategy we'll apply for solving problems:

- State the problem clearly. Identify the input & output formats.
- Come up with some example inputs & outputs. Try to cover all edge cases.
- Come up with a correct solution for the problem. State it in plain English.
- Implement the solution and test it using example inputs. Fix bugs, if any.
- Analyze the algorithm's complexity and identify inefficiencies, if any.
- Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

### Solution

#### 1. State the problem clearly. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

**Problem**

We need to find the maximum amount of profit we can achieve, within a certain number of transactions, where we can only engange in a single transaction at a time, until we reach the end of the prices array.

transaction profit = (price the stock is currently at) - (price at which we bought the stock)

final profit = the sum of all transaction profits

**Input**

`prices`

= an array of stock prices ordered in a chronological sequential manner, where the index represents the day at which the stock was values at that price`k`

= maximum number of transactions we are allowed to perform

**Output**

`profit`

= the maximum profit we can achieve

Based on the above, we can now create a signature of our function: