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:

1. State the problem clearly. Identify the input & output formats.
2. Come up with some example inputs & outputs. Try to cover all edge cases.
3. Come up with a correct solution for the problem. State it in plain English.
4. Implement the solution and test it using example inputs. Fix bugs, if any.
5. Analyze the algorithm's complexity and identify inefficiencies, if any.
6. 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

1. 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
2. k = maximum number of transactions we are allowed to perform

Output

1. profit = the maximum profit we can achieve

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