Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

Max profit with k transactions

In [1]:
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:

  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:

In [2]:
def calculate_max_profit(prices, k):
    pass

Save and upload your work before continuing.

2. Come up with some example inputs & outputs. Try to cover all edge cases.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. Single transaction which result in profit
  2. Single transaction with no way to profit
  3. Multiple transactions which result in profit
  4. Multiple transactions with no way to profit
  5. Situations were the inputs don't make sense, zero or negative number of max transactions and negative stock values

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [3]:
test1 = {
    'input': {
        'prices' : [1, 2, 1],
        'k' : 1
    },
    'output': 1
}
In [4]:
test2 = {
    'input': {
        'prices' : [3, 2, 1],
        'k' : 1
    },
    'output': 0
}
In [5]:
test3 = {
    'input': {
        'prices' : [3, 2, 6, 5, 0, 3],
        'k' : 2
    },
    'output': 7
}
In [6]:
test4 = {
    'input': {
        'prices' : [9, 7, 6, 5, 2, 1],
        'k' : 2
    },
    'output': 0
}
In [7]:
test5 = {
    'input': {
        'prices' : [-1, -2, -1],
        'k' : -1
    },
    'output': 0
}
In [8]:
test5 = {
    'input': {
        'prices' : [5, 11, 3, 50, 60, 90],
        'k' : 2
    },
    'output': 93
}
In [9]:
tests = [test1, test2, test3, test4, test5]

3. Come up with a correct solution for the problem. State it in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution.

Our problem has quite a lot of dimensionality when we think about it. Not only do we need to worry about the profit we gain if we were to sell on any particular day, but we also have to take into account any potential profits we could already have aquired from selling on previous days. In order to represent all of this intricacy we will need to create a 2D array to house all of our profit combinations, where the the row index represents the number of transactions we can make and the collumns index represent the max profit we could make up until that day.

Lets illustrate this by going through an example

prices  : [3, 2, 6, 5, 0, 3]
profits :[[0, 0, 0, 0, 0, 0],
          [0, 0, 4, 4, 4, 4],
          [0, 0, 4, 4, 4, 7]]

Our 2D profits array will be of size k + 1 * len(prices) - 1. Each value in the array will be filled with the maximum profit we can aquire up until that day with the given number of transactions specified by the row number.

When k = 0 we have no profits since no transactions can occur, so profits[0] = [0, 0, 0, 0, 0, 0].

When k = 1 we have:

  1. profits[1][0] = 0 since we cant make any transactions yet
  2. profits[1][1] = 0 since the only transaction we can make would be 2-3 which is <0 which is not profitable.
  3. profits[1][2] = 4 since the max profit at this day would be 6-2, same goes for the rest of the days since the price of the stock never goes above 6 so 6-2 is the best option we get profits[1] =[0, 0, 4, 4, 4, 4]

When k = 2 we mostly the same values as the ones when k = 1 since there is no combinations of transactions to get over a profit of 4, until we reach the last day where we have the combinations (6-2) + (3-0) = 7

Now the question on everyones minds should be how do we calculate this value algorithmically. Heres how:

profits[i][j] = max(profits[i][j-1], prices[j] + max(-prices[x] + profits[i-1][x])) where 0 <= x < j

So say we are on day 6 (j = 5) and we can make two transactions k= 2 (i = 2)

x = 0: -prices[0] + profits[1][0] = -3 + 0 = -3
x = 1: -prices[1] + profits[1][1] = -2 + 0 = -2
x = 2: -prices[2] + profits[1][2] = -6 + 4 = -2
x = 3: -prices[3] + profits[1][3] = -5 + 4 = -1
x = 4: -prices[4] + profits[1][4] = -0 + 4 = 4 => the max value

So our equations becomes:

profits[2][5] = max(profits[2][4], prices[5] + 4) = max(4, 3 + 4) = max(4, 7) = 7

Here are the steps we should take:

  1. Instantiate the profits array.
  2. Iterate from 0 to k + 1 to traverse the rows of profits
  3. Iterate from 0 to len(prices) to traverse the days of profits
  4. Iterate from 0 to current day and calculate max(-prices[x] + profit[i-1][x])
  5. Calculate max(profits[i][j-1], prices[j] + max(-prices[x] + profit[i-1][x]))
  6. The largest value of profits is our final result.

4. Implement the solution and test it using example inputs. Fix bugs, if any.

In [10]:
!pip install jovian --upgrade --quiet
In [11]:
import jovian
In [12]:
import numpy as np

def calculate_max_profit(prices, k, display_steps=False):
    
    # Instantiate the profits array
    profits = [[0] * len(prices) for _ in range(k + 1)]
        
    # Iterate over the number of transactions
    for i in range(k + 1):
        # Iterate over the days
        for j in range(len(prices)):
            # If we cant make any transactions set current profit to 0
            if i == 0 or j == 0:
                profits[i][j] = 0
            else:
                x_max = [max(-prices[x] + profits[i-1][x] for x in range(j))]
                # Calculate the max profit for the current day
                profits[i][j] = max(profits[i][j-1], prices[j] + max(x_max))
                if display_steps:
                    print('k=',i , 'day=', j, 'maxprofit=', profits[i][j])
    
    if display_steps:
        print(np.matrix(profits))            
    
    # Return the largest profit        
    return np.amax(profits)
In [13]:
def test_function(test, method, display_steps=False):
    inputs, output = test['input'], test['output']
    prices, k = inputs['prices'], inputs['k']
    print('Input:', inputs)
    print('Expected output:', output)
    result = method(prices, k, display_steps)
    print('Actual output:', result)
    print('Match:', result == output)
In [14]:
test_function(test1, calculate_max_profit, display_steps=True)
Input: {'prices': [1, 2, 1], 'k': 1} Expected output: 1 k= 1 day= 1 maxprofit= 1 k= 1 day= 2 maxprofit= 1 [[0 0 0] [0 1 1]] Actual output: 1 Match: True
In [15]:
test_function(test2, calculate_max_profit, display_steps=True)
Input: {'prices': [3, 2, 1], 'k': 1} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 [[0 0 0] [0 0 0]] Actual output: 0 Match: True
In [16]:
test_function(test3, calculate_max_profit, display_steps=True)
Input: {'prices': [3, 2, 6, 5, 0, 3], 'k': 2} Expected output: 7 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 4 k= 1 day= 3 maxprofit= 4 k= 1 day= 4 maxprofit= 4 k= 1 day= 5 maxprofit= 4 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 4 k= 2 day= 3 maxprofit= 4 k= 2 day= 4 maxprofit= 4 k= 2 day= 5 maxprofit= 7 [[0 0 0 0 0 0] [0 0 4 4 4 4] [0 0 4 4 4 7]] Actual output: 7 Match: True
In [17]:
test_function(test4, calculate_max_profit, display_steps=True)
Input: {'prices': [9, 7, 6, 5, 2, 1], 'k': 2} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 k= 1 day= 3 maxprofit= 0 k= 1 day= 4 maxprofit= 0 k= 1 day= 5 maxprofit= 0 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 0 k= 2 day= 3 maxprofit= 0 k= 2 day= 4 maxprofit= 0 k= 2 day= 5 maxprofit= 0 [[0 0 0 0 0 0] [0 0 0 0 0 0] [0 0 0 0 0 0]] Actual output: 0 Match: True
In [18]:
test_function(test5, calculate_max_profit, display_steps=True)
Input: {'prices': [5, 11, 3, 50, 60, 90], 'k': 2} Expected output: 93 k= 1 day= 1 maxprofit= 6 k= 1 day= 2 maxprofit= 6 k= 1 day= 3 maxprofit= 47 k= 1 day= 4 maxprofit= 57 k= 1 day= 5 maxprofit= 87 k= 2 day= 1 maxprofit= 6 k= 2 day= 2 maxprofit= 6 k= 2 day= 3 maxprofit= 53 k= 2 day= 4 maxprofit= 63 k= 2 day= 5 maxprofit= 93 [[ 0 0 0 0 0 0] [ 0 6 6 47 57 87] [ 0 6 6 53 63 93]] Actual output: 93 Match: True

5. Analyze the algorithm's complexity and identify inefficiencies.

Since we are creating and traversing a 2D array of profits, with size proportional to the length of our prices array and the number of transactions we are allowed to conduct, we would expect our time complexity to be O(len(prices) * (k + 1)).

However for each iteration of our 2D array we also have to iterate over past profits gained from previous numbers of transactions, and this number can vary between 0 and len(prices).

Since we will only consider the worst case scenario this leads to our time complexity actually being O(len(prices)^2 * (k+1))

Lets just call it O(n^2 * m)

Meanwhile our space complexity will be O(n*m) since that is the size of the array we are working with will depend on length of prices and number of transactions k.

In [19]:
time_complexity = 'O(n^2 * m)'
In [20]:
space_complexity = 'O(n * m)'

6. Apply the right technique to overcome the inefficiency.

Our time complexity is currently quadratinc, this is generally regarded as horrible.

Our space complexity is linear, which would generally be fair but could be better.

However there are a few ways for us to improve this through the application of a DYNAMIC PROGRAMMING concept called MEMOIZATION.

If we take a look at our algorith one more time max(profits[i][j-1], prices[j] + max(-prices[x] + profit[i-1][x])) specifically to the max(-prices[x] + profit[i-1][x]) section, remeber that 0 <= x < j, we notice that we are repeating a lof of the same calculations. Instead of recalculating max(-prices[x] + profit[i-1][x]) for each single day, we save the previous days max, compare it to the current days value and take the max between them.

This will completely get rid of the need to iterate for 0 <= x < j and bring our time complexity down to O(n*m)

7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

  1. Instantiate the profits array.
  2. Iterate from 0 to k + 1 to traverse the rows of profits
  3. Iterate from 0 to len(prices) to traverse the days of profits
  4. Calculate max(-prices[x] + profit[i-1][x]) and save it
  5. Calculate max(profits[i][j-1], prices[j] + max_so_far)
  6. The largest value of profits is our final result

8. Implement the solution and test it using example inputs. Fix bugs, if any.

In [21]:
import sys

def calculate_max_profit_time_optimized(prices, k, display_steps=False):
    
    # Instantiate the profits array
    profits = [[0] * len(prices) for _ in range(k + 1)]
        
    # Iterate over the number of transactions
    for i in range(k + 1):
        # The variable where we will store our x_max initialized to the smalles possible integer
        max_so_far = -sys.maxsize - 1
        # Iterate over the days
        for j in range(len(prices)):
            # If we cant make any transactions set current profit to 0
            if i == 0 or j == 0:
                profits[i][j] = 0
            else:
                max_so_far = max(max_so_far, -prices[j-1] + profits[i-1][j-1])
                # Calculate the max profit for the current day
                profits[i][j] = max(profits[i][j-1], prices[j] + max_so_far)
                if display_steps:
                    print('k=',i , 'day=', j, 'maxprofit=', profits[i][j])
    
    if display_steps:
        print(np.matrix(profits))            
    
    # Return the largest profit        
    return np.amax(profits)
In [22]:
test_function(test1, calculate_max_profit_time_optimized, display_steps=True)
Input: {'prices': [1, 2, 1], 'k': 1} Expected output: 1 k= 1 day= 1 maxprofit= 1 k= 1 day= 2 maxprofit= 1 [[0 0 0] [0 1 1]] Actual output: 1 Match: True
In [23]:
test_function(test2, calculate_max_profit_time_optimized, display_steps=True)
Input: {'prices': [3, 2, 1], 'k': 1} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 [[0 0 0] [0 0 0]] Actual output: 0 Match: True
In [24]:
test_function(test3, calculate_max_profit_time_optimized, display_steps=True)
Input: {'prices': [3, 2, 6, 5, 0, 3], 'k': 2} Expected output: 7 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 4 k= 1 day= 3 maxprofit= 4 k= 1 day= 4 maxprofit= 4 k= 1 day= 5 maxprofit= 4 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 4 k= 2 day= 3 maxprofit= 4 k= 2 day= 4 maxprofit= 4 k= 2 day= 5 maxprofit= 7 [[0 0 0 0 0 0] [0 0 4 4 4 4] [0 0 4 4 4 7]] Actual output: 7 Match: True
In [25]:
test_function(test4, calculate_max_profit_time_optimized, display_steps=True)
Input: {'prices': [9, 7, 6, 5, 2, 1], 'k': 2} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 k= 1 day= 3 maxprofit= 0 k= 1 day= 4 maxprofit= 0 k= 1 day= 5 maxprofit= 0 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 0 k= 2 day= 3 maxprofit= 0 k= 2 day= 4 maxprofit= 0 k= 2 day= 5 maxprofit= 0 [[0 0 0 0 0 0] [0 0 0 0 0 0] [0 0 0 0 0 0]] Actual output: 0 Match: True
In [26]:
test_function(test5, calculate_max_profit_time_optimized, display_steps=True)
Input: {'prices': [5, 11, 3, 50, 60, 90], 'k': 2} Expected output: 93 k= 1 day= 1 maxprofit= 6 k= 1 day= 2 maxprofit= 6 k= 1 day= 3 maxprofit= 47 k= 1 day= 4 maxprofit= 57 k= 1 day= 5 maxprofit= 87 k= 2 day= 1 maxprofit= 6 k= 2 day= 2 maxprofit= 6 k= 2 day= 3 maxprofit= 53 k= 2 day= 4 maxprofit= 63 k= 2 day= 5 maxprofit= 93 [[ 0 0 0 0 0 0] [ 0 6 6 47 57 87] [ 0 6 6 53 63 93]] Actual output: 93 Match: True

All looks good, now lets fix our space complexity. Our space complexity is currently O(n * m) which is linear and fair. But if we consider a very large prices array where we can condunt a very large number of transactions, our profits array starts looking quite large and hard to manage. However there is a way to reduce the slope of our space complexities linearity. The smaller the slope, the more efficiet our space usage is.

If we take a look at our profits array and our algorith again, we will notice that at any moment in time we are never working with more than two rows from our profits array.

max_so_far = max(max_so_far, -prices[j-1] + profits[i-1][j-1])

profits[i][j] = max(profits[i][j-1], prices[j] + max_so_far)

We are always restricted to the i-1th and ith rows. So there is no reason to create a n*m array, we can simply use two 1D arrays where we store the profits from the previous k-1 transactions and the current k transactions and once we finished all the values for the current k we make k-1 array equal to the k array and move on to calculate the values of the next row.

Let's implement this now.

In [27]:
import sys

def calculate_max_profit_time_and_space_optimized(prices, k, display_steps=False):
    
    # Instantiate the profits arrays
    profits_last_k = [0] * len(prices)
    profits_current_k = [0] * len(prices)
        
    # Iterate over the number of transactions
    for i in range(1, k + 1):
        # The variable where we will store our x_max, initialized to the smalles possible integer
        max_so_far = -sys.maxsize - 1
        # Iterate over the days
        for j in range(len(prices)):
            # If we cant make any transactions set current profit to 0
            if j == 0:
                profits_current_k[j] = 0
            else:
                max_so_far = max(max_so_far, -prices[j-1] + profits_last_k[j-1])
                # Calculate the max profit for the current day
                profits_current_k[j] = max(profits_current_k[j-1], prices[j] + max_so_far)
                if display_steps:
                    print('k=',i , 'day=', j, 'maxprofit=', profits_current_k[j])
        
        profits_last_k = profits_current_k
    
    if display_steps:
        print(profits_current_k)
    
    # Return the largest profit
    return max(profits_current_k)
In [28]:
test_function(test1, calculate_max_profit_time_and_space_optimized, display_steps=True)
Input: {'prices': [1, 2, 1], 'k': 1} Expected output: 1 k= 1 day= 1 maxprofit= 1 k= 1 day= 2 maxprofit= 1 [0, 1, 1] Actual output: 1 Match: True
In [29]:
test_function(test2, calculate_max_profit_time_and_space_optimized, display_steps=True)
Input: {'prices': [3, 2, 1], 'k': 1} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 [0, 0, 0] Actual output: 0 Match: True
In [30]:
test_function(test3, calculate_max_profit_time_and_space_optimized, display_steps=True)
Input: {'prices': [3, 2, 6, 5, 0, 3], 'k': 2} Expected output: 7 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 4 k= 1 day= 3 maxprofit= 4 k= 1 day= 4 maxprofit= 4 k= 1 day= 5 maxprofit= 4 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 4 k= 2 day= 3 maxprofit= 4 k= 2 day= 4 maxprofit= 4 k= 2 day= 5 maxprofit= 7 [0, 0, 4, 4, 4, 7] Actual output: 7 Match: True
In [31]:
test_function(test4, calculate_max_profit_time_and_space_optimized, display_steps=True)
Input: {'prices': [9, 7, 6, 5, 2, 1], 'k': 2} Expected output: 0 k= 1 day= 1 maxprofit= 0 k= 1 day= 2 maxprofit= 0 k= 1 day= 3 maxprofit= 0 k= 1 day= 4 maxprofit= 0 k= 1 day= 5 maxprofit= 0 k= 2 day= 1 maxprofit= 0 k= 2 day= 2 maxprofit= 0 k= 2 day= 3 maxprofit= 0 k= 2 day= 4 maxprofit= 0 k= 2 day= 5 maxprofit= 0 [0, 0, 0, 0, 0, 0] Actual output: 0 Match: True
In [32]:
test_function(test5, calculate_max_profit_time_and_space_optimized, display_steps=True)
Input: {'prices': [5, 11, 3, 50, 60, 90], 'k': 2} Expected output: 93 k= 1 day= 1 maxprofit= 6 k= 1 day= 2 maxprofit= 6 k= 1 day= 3 maxprofit= 47 k= 1 day= 4 maxprofit= 57 k= 1 day= 5 maxprofit= 87 k= 2 day= 1 maxprofit= 6 k= 2 day= 2 maxprofit= 6 k= 2 day= 3 maxprofit= 53 k= 2 day= 4 maxprofit= 63 k= 2 day= 5 maxprofit= 93 [0, 6, 6, 53, 63, 93] Actual output: 93 Match: True

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

We have succesfully reduced the time complexity of our algorithm to O(n*m) and our space complexity to O(n)

In [33]:
optimized_time_complexity = 'O(n*m)'
In [34]:
optimized_space_complexity = 'O(n)'

Lets run some benchmarks and compare all three approaches to see how much each one of our optimization steps has helped. We will create a large array of prices with random integer numbers in order to compare all our algorithms.

In [35]:
import random

# Lets create a very long list of random integer values for testing
prices = []
k = 1000
for i in range(0, k):
    n = random.randint(0, 30)
    prices.append(n)
print(prices)

# Since we can't tell what the actual output will be, we wont care if the test passes, we are only interested in execution time
benchmark_test = {
    'input':{
        'prices': prices,
        'k': k
    },
    'output': 0
}
[26, 24, 30, 15, 0, 3, 4, 27, 11, 0, 9, 26, 8, 26, 10, 3, 22, 7, 7, 3, 4, 3, 10, 4, 27, 3, 27, 15, 4, 18, 19, 11, 5, 0, 15, 15, 3, 21, 9, 13, 5, 29, 16, 9, 29, 10, 12, 27, 19, 15, 28, 5, 15, 28, 8, 26, 2, 28, 3, 7, 8, 14, 19, 15, 24, 23, 18, 16, 24, 9, 19, 1, 8, 29, 28, 26, 3, 20, 24, 3, 20, 3, 0, 18, 20, 18, 25, 1, 17, 21, 12, 8, 2, 25, 11, 24, 3, 17, 17, 10, 25, 17, 2, 26, 5, 24, 19, 17, 10, 28, 11, 7, 1, 20, 1, 29, 28, 30, 25, 30, 9, 7, 27, 6, 16, 16, 2, 4, 26, 7, 25, 4, 9, 25, 22, 11, 19, 1, 3, 9, 7, 6, 21, 18, 1, 8, 12, 18, 22, 6, 25, 1, 20, 5, 0, 5, 20, 4, 7, 27, 6, 2, 26, 29, 8, 14, 8, 19, 4, 5, 8, 4, 22, 15, 16, 29, 26, 3, 2, 28, 27, 29, 21, 0, 16, 26, 0, 22, 15, 4, 13, 19, 3, 1, 2, 20, 6, 16, 30, 28, 18, 29, 22, 11, 7, 29, 20, 21, 25, 22, 9, 13, 28, 9, 1, 22, 1, 5, 15, 4, 27, 14, 28, 19, 8, 16, 7, 8, 0, 27, 6, 11, 16, 12, 14, 19, 26, 0, 7, 5, 14, 22, 18, 25, 6, 15, 13, 2, 16, 9, 13, 19, 23, 17, 21, 27, 17, 3, 16, 1, 28, 27, 24, 18, 29, 9, 26, 23, 16, 15, 22, 28, 13, 4, 11, 6, 28, 2, 20, 15, 13, 2, 28, 28, 0, 24, 9, 16, 24, 28, 26, 8, 17, 29, 22, 18, 3, 17, 25, 3, 24, 15, 1, 19, 12, 7, 2, 8, 30, 4, 18, 0, 6, 22, 24, 30, 1, 26, 3, 10, 4, 0, 4, 23, 26, 17, 19, 26, 28, 25, 6, 14, 12, 30, 14, 6, 3, 18, 2, 29, 12, 4, 9, 16, 16, 18, 13, 7, 14, 29, 1, 27, 28, 28, 8, 29, 2, 7, 0, 4, 24, 30, 14, 21, 20, 1, 30, 2, 5, 19, 30, 2, 6, 5, 21, 19, 9, 30, 24, 19, 7, 5, 28, 13, 5, 25, 4, 26, 20, 24, 20, 1, 18, 30, 18, 0, 12, 15, 30, 14, 3, 12, 20, 22, 15, 1, 26, 3, 2, 7, 6, 7, 3, 26, 8, 0, 8, 19, 5, 18, 6, 29, 15, 22, 2, 20, 27, 26, 21, 19, 10, 26, 23, 20, 3, 3, 26, 20, 15, 13, 17, 16, 26, 13, 21, 30, 28, 26, 19, 14, 24, 18, 28, 26, 27, 17, 30, 14, 3, 8, 20, 0, 8, 27, 21, 15, 29, 16, 28, 9, 1, 2, 29, 2, 29, 28, 18, 17, 7, 13, 21, 16, 22, 11, 18, 8, 9, 22, 30, 10, 15, 0, 6, 21, 21, 1, 6, 23, 4, 5, 20, 29, 15, 7, 16, 9, 15, 19, 2, 21, 30, 23, 13, 28, 3, 18, 7, 12, 17, 2, 7, 15, 1, 3, 27, 25, 25, 28, 10, 24, 1, 13, 18, 21, 14, 10, 6, 16, 14, 9, 29, 9, 29, 7, 3, 1, 28, 27, 14, 10, 16, 19, 10, 16, 25, 8, 14, 17, 11, 3, 11, 4, 0, 16, 7, 1, 16, 12, 17, 17, 18, 2, 11, 16, 22, 19, 3, 9, 8, 3, 22, 2, 12, 3, 19, 27, 2, 4, 1, 9, 12, 30, 1, 10, 13, 20, 15, 5, 25, 17, 13, 16, 9, 19, 2, 17, 8, 4, 2, 19, 23, 18, 25, 0, 7, 25, 19, 5, 11, 0, 10, 2, 17, 23, 30, 6, 5, 1, 10, 2, 30, 23, 9, 24, 23, 9, 9, 8, 23, 22, 5, 26, 0, 23, 16, 27, 10, 4, 7, 20, 12, 5, 7, 16, 17, 29, 19, 18, 27, 2, 20, 17, 13, 4, 14, 9, 4, 23, 24, 26, 26, 17, 6, 26, 19, 19, 6, 4, 2, 21, 5, 27, 6, 11, 24, 17, 4, 21, 3, 20, 9, 8, 6, 5, 5, 9, 3, 1, 29, 5, 20, 27, 14, 25, 3, 15, 1, 21, 13, 19, 4, 6, 3, 29, 8, 6, 16, 3, 25, 7, 3, 27, 12, 6, 10, 30, 24, 13, 5, 9, 16, 7, 23, 25, 25, 14, 17, 18, 8, 12, 11, 7, 15, 0, 21, 2, 20, 21, 27, 20, 19, 18, 29, 0, 20, 14, 11, 1, 21, 23, 8, 4, 7, 30, 22, 13, 9, 15, 28, 10, 23, 20, 24, 9, 30, 6, 23, 15, 10, 17, 28, 24, 22, 11, 10, 0, 19, 20, 28, 10, 9, 28, 3, 2, 8, 6, 18, 0, 13, 6, 6, 13, 1, 7, 25, 3, 6, 0, 24, 8, 27, 24, 0, 0, 14, 18, 19, 28, 0, 14, 28, 22, 24, 12, 4, 25, 28, 9, 4, 23, 7, 11, 25, 19, 1, 5, 17, 16, 11, 21, 23, 7, 11, 12, 12, 24, 12, 15, 30, 8, 7, 18, 23, 15, 2, 14, 24, 17, 20, 24, 24, 27, 15, 13, 6, 10, 28, 22, 4, 5, 20, 8, 1, 14, 19, 1, 2, 29, 22, 25, 20, 24, 14, 14, 17, 14, 11, 14, 1, 15, 8, 21, 14, 14, 9, 21, 4, 26, 11, 15, 3, 18, 20, 13, 5, 2, 20, 2, 17, 20, 6, 12, 3, 17, 0, 1, 24, 29, 9, 25, 16, 17, 21, 15, 21, 24, 0, 7, 6, 5, 30, 27, 23, 24, 18, 10, 15, 11, 2, 0, 21, 18, 25, 28, 22, 20, 28, 7, 13, 17, 7, 1, 1, 14, 21, 9, 29, 12, 15, 18, 9, 27, 25, 22, 3, 20, 24, 12, 9, 30, 0, 6, 0, 7, 5, 19, 0, 10, 20, 25, 15, 9, 22, 14, 2, 6, 10, 16, 21, 26, 26, 6, 1, 22, 12, 4, 15, 17, 13, 10]
In [36]:
from jovian.pythondsa import evaluate_test_cases
In [37]:
evaluate_test_cases(calculate_max_profit, [benchmark_test])
TEST CASE #0 Input: {'prices': [26, 24, 30, 15, 0, 3, 4, 27, 11, 0, 9, 26, 8, 26, 10, 3, 22, 7, 7, 3, 4, 3, 10, 4, 27, 3... Expected Output: 0 Actual Output: 5132 Execution Time: 85941.616 ms Test Result: FAILED SUMMARY TOTAL: 1, PASSED: 0, FAILED: 1
Out[37]:
[(5132, False, 85941.616)]
In [38]:
evaluate_test_cases(calculate_max_profit_time_optimized, [benchmark_test])
TEST CASE #0 Input: {'prices': [26, 24, 30, 15, 0, 3, 4, 27, 11, 0, 9, 26, 8, 26, 10, 3, 22, 7, 7, 3, 4, 3, 10, 4, 27, 3... Expected Output: 0 Actual Output: 5132 Execution Time: 761.235 ms Test Result: FAILED SUMMARY TOTAL: 1, PASSED: 0, FAILED: 1
Out[38]:
[(5132, False, 761.235)]
In [39]:
evaluate_test_cases(calculate_max_profit_time_and_space_optimized, [benchmark_test])
TEST CASE #0 Input: {'prices': [26, 24, 30, 15, 0, 3, 4, 27, 11, 0, 9, 26, 8, 26, 10, 3, 22, 7, 7, 3, 4, 3, 10, 4, 27, 3... Expected Output: 0 Actual Output: 5132 Execution Time: 599.75 ms Test Result: FAILED SUMMARY TOTAL: 1, PASSED: 0, FAILED: 1
Out[39]:
[(5132, False, 599.75)]

As we can see, the difference is VERY remarkable, between the unoptimized solution and the time optimized one.

It also seems that we gained a bit of speed from our space optimization as well. Makes sense since searching for information through a small amount of memory will always be faster than searching for the same information in a large amout of memory.

In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..
In [ ]: