Max Profit With K Transactions
Max profit with k transactions
project_name = "max-profit-with-k-transactions"
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) the price of the stock was 3 on day 1 (prices) the price of the stock was 8 on day 2 (prices) 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.
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.
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.
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
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
profit= the maximum profit we can achieve
Based on the above, we can now create a signature of our function: