Jovian
⭐️
Sign In

Jovian DSA Course Project - Stock Maximize

This is the course project created for the online course "Data Structures and Algorithms in Python". The problem that we will analyze in this notebook is 'Stock Maximize' taken from "HackerRank".

How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [1]:
project_name = 'dsa-course-project' # give it an appropriate name
In [2]:
!pip install jovian --upgrade --quiet
In [3]:
import jovian
In [4]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project

Problem Statement

Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next number of days. Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?

Example
prices=[1,2]
Buy one share day one, and sell it day two for a profit of 1. Return 1.

prices=[2,1]
No profit can be made so you do not buy or sell stock those days. Return 0.

Source: https://www.hackerrank.com/challenges/stockmax/problem (link to the source)

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

In this problem we have a number of test cases \(t\) and an array \(n\) that contains \(t\) numbers that depict the days the stock prices are predicted and finally \(prices\) is the 2-D array with the stock prices for each day for each test case. The main goal is to find for every test case the optimal policy of buying stock, selling or doing nothing. The key is to find when the stock gets the maximum value in order to sell it that day and earn maximum profit. We consider that when the price does not rise anymore we buy and sell in order to not lose any profit.


Input

  1. t: the number of test cases \(1\leq t\leq 10\)
  2. n: number of predicted prices \(1\leq n\leq 50000\)
  3. prices: two dimensional array containing predicted stock price for day each day i where \(1\leq prices[i]\leq 100000\)

Output

  1. res: array containing the maximum profit which can be obtained for the corresponding test case.

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

In [5]:
# Create a function signature here. The body of the function can contain a single statement: pass
def stockMax(t,n,prices):
    pass

Save and upload your work before continuing.

In [6]:
import jovian
In [7]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project

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. Number of test cases: 3, Number of days:3,3 and 4, Prices of the stock for each day where first test returns zero as there is no profit to gain, second returns 197 profit for buying first two days and selling the third both stocks for 100 each, and third returns 3 for buying and selling each day for four days
  2. Number of test cases: 2, Number of days: 4 and 5, Prices of the stock for each day and expected output 6 for first test and 4 for second
  3. Number of test cases: 5, Number of days: [10,2,6,3,4], Prices of the stock for each day [[1,10,12,8,9,17,16,11,19,17],[4,7],[10,13,1,16,12,16],[10,7,9],[11,15,13,13]] and expected output [68, 3, 28, 2, 4]
  4. Number of test cases: 2, Number of days: [100,500], Prices of the stock for each day and expected output [84172, 1234923]
  5. Number of test cases: 8, Number of days: [50,150,200,300,500,600,800,1000], Prices of the stock for each day and expected output [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821]
  6. Number of test cases: 5, Number of days: [2,4,6,8,10], Prices of the stock for each day [[3,6],[3,5,2,9],[7,9,4,13,2,12],[0, 7, 5, 8, 6, 16, 8, 13],[13, 33, 15, 16, 18, 34, 37, 28, 2, 27]] and expected output [3, 17, 29, 59, 118]
  7. Number of test cases is 0 which is not accepted an should return message "Error"
  8. Number of test cases: 1, Number of days: [1], Prices of the stock for each day [[10]] and expected output [0]

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 [8]:
test0 = {
    'input': {
        't':3,
        'n':[3,3,4],
        'prices':[[5,3,2],[1,2,100],[1,3,1,2]]
    },
    'output': [0,197,3]
}
In [9]:
test1 = {
    'input': {
        't':2,
        'n':[4,5],
        'prices':[[1,2,3,4],[5,4,3,4,5]]
    },
    'output': [6, 4]
}
In [10]:
test2 = {
    'input': {
        't':5,
        'n':[10,2,6,3,4],
        'prices':[[1,10,12,8,9,17,16,11,19,17],[4,7],[10,13,1,16,12,16],[10,7,9],[11,15,13,13]]
    },
    'output': [68, 3, 28, 2, 4]
}
In [11]:
test3 = {
    'input': {
        't':2,
        'n':[100,500],
        'prices':[[644, 1011, 1344, 1368, 870, 520, 367, 1864, 1319, 1751, 999, 1649, 1268, 1768, 897, 953, 1169, 182, 209, 549, 1016, 1208, 285, 435, 544, 1518, 672, 433, 3, 1802, 1806, 1591, 1855, 207, 879, 643, 1607, 401, 1594, 1492, 762, 1459, 155, 468, 1402, 1603, 651, 1641, 1145, 1646, 413, 1182, 1935, 348, 19, 437, 1594, 776, 745, 588, 1628, 1090, 293, 282, 240, 1462, 316, 1387, 1833, 1767, 94, 537, 1679, 1693, 667, 1194, 1384, 195, 1140, 1592, 487, 745, 823, 125, 1438, 671, 1849, 1580, 66, 1872, 1860, 1735, 1076, 811, 68, 762, 324, 817, 985, 722],[2494, 304, 3945, 1012, 1638, 2908, 136, 4284, 4933, 4847, 2601, 525, 331, 342, 2641, 549, 2418, 1003, 3404, 103, 3786, 3058, 3351, 2690, 3505, 902, 2352, 1598, 4743, 2197, 1046, 1478, 3986, 4478, 4724, 4306, 4372, 2164, 80, 1186, 1230, 1986, 4627, 762, 2578, 2657, 2385, 3168, 4343, 2175, 4058, 709, 637, 33, 3847, 4888, 2383, 2421, 2027, 2660, 765, 3424, 4840, 2352, 4492, 65, 860, 1715, 3837, 3548, 3735, 2719, 2985, 356, 1212, 1290, 1230, 3162, 3956, 2019, 3164, 752, 204, 272, 71, 3810, 1994, 1464, 1968, 4407, 2969, 2240, 4599, 2656, 4202, 3496, 1070, 3681, 1474, 3651, 899, 3031, 404, 1635, 3767, 767, 4325, 4557, 2575, 1370, 1290, 4587, 52, 4006, 4134, 2095, 149, 132, 832, 2260, 4345, 168, 4791, 3646, 4725, 2433, 2398, 2996, 1290, 1602, 710, 413, 1634, 1543, 4249, 50, 234, 1138, 2317, 4140, 2566, 2997, 504, 4290, 2830, 2917, 3637, 4347, 4042, 1575, 2832, 1580, 4093, 3735, 3356, 2451, 4183, 4207, 1717, 2790, 2471, 2485, 4659, 1738, 1034, 4168, 3784, 156, 2607, 2343, 4325, 2909, 3460, 1784, 2766, 353, 3377, 2649, 401, 4018, 2043, 1458, 232, 1670, 4481, 149, 2779, 951, 2098, 282, 3369, 1932, 132, 2185, 3188, 803, 587, 1140, 765, 2117, 3111, 965, 3017, 1060, 3793, 4731, 2195, 4439, 3221, 4158, 73, 4713, 2888, 35, 687, 4889, 345, 303, 3869, 3436, 3641, 2776, 4477, 634, 777, 1573, 2610, 2222, 878, 1827, 4892, 2746, 4401, 3468, 3832, 4994, 4440, 1669, 3440, 2157, 3722, 110, 1515, 4933, 3750, 1525, 1630, 1136, 3405, 3853, 2681, 4175, 4730, 2254, 2105, 353, 3313, 4297, 1076, 1280, 2461, 1170, 2092, 1742, 1740, 2567, 2612, 639, 2810, 2004, 1175, 2111, 2377, 1580, 4785, 2858, 98, 505, 4610, 2897, 646, 1541, 4194, 2259, 862, 3636, 206, 4114, 1495, 4841, 4267, 1744, 3221, 470, 1554, 2659, 1021, 129, 2378, 3921, 4084, 823, 2419, 2370, 2459, 1998, 1942, 27, 2128, 4822, 2372, 1348, 1001, 2950, 2969, 4261, 4069, 1704, 3597, 4283, 2068, 486, 3215, 2147, 4776, 892, 186, 4132, 668, 3278, 4542, 909, 4415, 4157, 2008, 2734, 2704, 2947, 1961, 2935, 2689, 4359, 573, 788, 3621, 1182, 3054, 1555, 671, 901, 4133, 1455, 408, 1585, 4224, 2139, 4675, 4977, 1138, 1011, 1694, 3711, 4025, 1080, 2231, 2647, 164, 22, 460, 1083, 4514, 129, 3358, 2115, 2574, 2599, 1186, 1564, 4789, 1668, 1237, 2228, 464, 1115, 4383, 4897, 4269, 3568, 2482, 1592, 4593, 1742, 3891, 1170, 3482, 1108, 2355, 1430, 929, 1329, 517, 1910, 3559, 1655, 222, 546, 1121, 4626, 2173, 76, 3795, 1357, 93, 4442, 1324, 3213, 613, 3833, 4095, 3198, 2847, 3038, 580, 3084, 4661, 577, 3051, 1462, 2434, 1158, 3104, 3601, 2399, 2792, 4932, 1973, 1479, 4663, 1637, 3297, 4259, 3632, 4087, 3365, 4631, 116, 2485, 3955, 4548, 1466, 3242, 3134, 2724, 4524, 3067, 1576, 2654, 3991, 4170, 2620, 4311, 2358, 3803, 2809, 4115, 4330, 1874, 3072, 1372, 2672, 2253, 3402, 2446, 3046, 4699, 1372, 2494, 4593, 1343, 3583, 2669, 4051, 1035, 1737, 4574, 2404, 3388, 3656, 1463, 1301, 1471, 685, 2806, 2084, 3504, 2514, 4687, 3376, 1633, 4289]]
    },
    'output': [84172, 1234923]
}
In [12]:
test4 = {
    'input': {
        't':8,
        'n':[50,150,200,300,500,600,800,1000],
        'prices':[[29, 20, 10, 18, 17, 15, 21, 25, 0, 21, 1, 46, 19, 14, 9, 23, 28, 7, 11, 0, 12, 14, 24, 11, 15, 44, 32, 18, 15, 45, 20, 17, 24, 43, 47, 21, 21, 14, 4, 1, 38, 38, 2, 13, 49, 26, 2, 22, 5, 18],
                 [201, 168, 259, 200, 103, 53, 39, 97, 229, 209, 257, 290, 40, 128, 171, 108, 3, 177, 143, 219, 213, 170, 200, 295, 76, 169, 252, 99, 174, 166, 59, 287, 153, 241, 236, 212, 194, 45, 272, 241, 140, 144, 93, 102, 72, 62, 29, 87, 165, 208, 212, 151, 292, 170, 159, 292, 66, 288, 85, 95, 242, 31, 150, 13, 219, 131, 254, 298, 136, 103, 61, 278, 204, 14, 36, 82, 8, 54, 46, 196, 53, 118, 294, 164, 86, 118, 292, 33, 3, 210, 56, 160, 80, 124, 208, 274, 269, 119, 297, 74, 241, 91, 168, 53, 94, 29, 295, 257, 85, 252, 93, 15, 166, 57, 203, 158, 50, 76, 155, 222, 86, 47, 194, 255, 162, 112, 56, 138, 133, 32, 151, 126, 89, 54, 13, 97, 206, 163, 289, 284, 94, 288, 284, 13, 192, 173, 157, 44, 205, 214],
                 [3, 343, 416, 110, 781, 22, 339, 537, 511, 769, 7, 752, 300, 56, 116, 296, 124, 548, 725, 623, 619, 781, 753, 552, 174, 727, 507, 557, 142, 382, 120, 558, 700, 86, 300, 18, 399, 624, 288, 393, 312, 495, 450, 655, 175, 252, 567, 536, 192, 279, 566, 376, 475, 15, 712, 738, 545, 328, 301, 694, 178, 195, 733, 617, 569, 298, 265, 238, 449, 618, 433, 192, 132, 458, 162, 332, 219, 722, 566, 680, 374, 653, 287, 596, 314, 501, 210, 469, 500, 365, 54, 529, 37, 770, 443, 555, 234, 616, 441, 148, 745, 39, 193, 147, 735, 403, 367, 368, 525, 125, 668, 110, 790, 675, 420, 650, 537, 97, 484, 457, 695, 331, 757, 46, 48, 442, 282, 645, 789, 630, 653, 370, 725, 235, 155, 386, 587, 405, 500, 175, 770, 598, 545, 84, 541, 752, 347, 235, 438, 61, 405, 563, 2, 113, 279, 784, 311, 32, 176, 653, 44, 459, 430, 714, 211, 313, 619, 555, 643, 280, 306, 540, 373, 692, 612, 716, 797, 444, 230, 254, 625, 711, 132, 542, 782, 746, 384, 62, 362, 636, 402, 179, 456, 241, 443, 226, 749, 386, 580, 53],
                 [733, 150, 755, 472, 429, 640, 737, 608, 599, 780, 547, 551, 340, 294, 657, 241, 76, 7, 259, 524, 865, 714, 154, 380, 479, 671, 297, 126, 276, 330, 117, 1, 762, 375, 56, 647, 398, 499, 181, 259, 520, 397, 374, 487, 652, 557, 16, 6, 90, 465, 804, 89, 688, 882, 146, 372, 641, 726, 725, 745, 414, 836, 164, 530, 745, 550, 455, 727, 254, 397, 231, 189, 214, 776, 261, 544, 346, 659, 640, 723, 96, 208, 886, 302, 583, 880, 220, 866, 874, 158, 389, 882, 47, 884, 734, 781, 10, 632, 633, 246, 856, 729, 736, 640, 455, 303, 869, 80, 333, 735, 208, 440, 45, 849, 642, 766, 74, 514, 772, 54, 746, 617, 866, 408, 893, 500, 55, 354, 573, 475, 450, 247, 648, 292, 834, 732, 733, 72, 470, 287, 117, 162, 473, 830, 682, 276, 88, 253, 40, 317, 532, 694, 200, 898, 191, 789, 880, 805, 86, 545, 671, 203, 459, 695, 46, 411, 419, 564, 458, 808, 459, 611, 621, 778, 443, 394, 639, 471, 806, 645, 232, 695, 687, 111, 433, 678, 147, 547, 459, 143, 20, 859, 30, 745, 677, 688, 155, 723, 85, 365, 155, 623, 51, 884, 183, 276, 42, 446, 293, 824, 32, 115, 92, 696, 428, 164, 13, 476, 501, 674, 847, 384, 89, 599, 191, 468, 844, 285, 118, 190, 476, 11, 61, 84, 809, 853, 67, 366, 775, 392, 717, 823, 167, 375, 808, 744, 696, 412, 812, 628, 6, 808, 803, 0, 203, 851, 393, 257, 131, 740, 616, 409, 47, 675, 192, 375, 452, 763, 171, 468, 310, 325, 37, 887, 692, 270, 725, 396, 419, 418, 510, 768, 412, 458, 51, 78, 398, 675, 143, 402, 491, 348, 5, 338, 118, 0, 589, 878, 417, 347],
                 [286, 333, 320, 251, 817, 502, 85, 622, 165, 471, 389, 543, 456, 13, 739, 818, 73, 608, 788, 492, 501, 769, 120, 415, 481, 715, 361, 428, 802, 877, 811, 486, 288, 254, 278, 841, 506, 129, 257, 10, 720, 367, 153, 184, 457, 181, 260, 510, 716, 582, 851, 164, 819, 869, 739, 716, 149, 87, 225, 208, 395, 653, 559, 837, 754, 294, 536, 147, 788, 183, 849, 790, 497, 446, 74, 634, 369, 364, 404, 585, 243, 435, 151, 31, 337, 242, 694, 694, 285, 896, 867, 233, 683, 172, 350, 679, 480, 589, 320, 365, 884, 211, 765, 241, 892, 731, 489, 244, 6, 595, 238, 265, 673, 507, 290, 74, 456, 128, 341, 399, 834, 93, 127, 174, 599, 519, 463, 47, 173, 497, 477, 234, 165, 499, 582, 685, 572, 254, 326, 113, 422, 607, 746, 526, 629, 710, 273, 529, 478, 736, 717, 139, 420, 861, 827, 65, 794, 154, 543, 53, 888, 172, 742, 413, 581, 746, 340, 63, 727, 796, 241, 274, 802, 369, 66, 811, 692, 434, 674, 792, 373, 883, 828, 40, 689, 735, 199, 16, 866, 194, 853, 630, 617, 46, 603, 435, 824, 310, 500, 418, 748, 874, 98, 164, 79, 126, 423, 746, 262, 479, 98, 251, 782, 477, 649, 787, 694, 195, 51, 110, 363, 157, 645, 523, 843, 364, 646, 52, 801, 610, 34, 423, 44, 818, 815, 125, 598, 333, 296, 155, 167, 838, 180, 321, 178, 451, 872, 795, 790, 522, 595, 40, 584, 195, 542, 715, 229, 679, 134, 725, 833, 590, 539, 302, 523, 773, 413, 405, 798, 784, 750, 188, 546, 370, 553, 201, 706, 161, 118, 422, 459, 819, 492, 138, 417, 2, 236, 416, 866, 23, 719, 767, 133, 803, 747, 744, 174, 98, 243, 531, 29, 652, 889, 96, 553, 76, 822, 550, 866, 66, 500, 55, 519, 142, 311, 294, 694, 442, 812, 317, 124, 807, 127, 382, 635, 434, 122, 533, 26, 234, 646, 529, 403, 865, 236, 339, 437, 567, 224, 491, 290, 138, 235, 647, 506, 529, 509, 491, 548, 308, 845, 824, 511, 583, 887, 660, 450, 622, 868, 96, 254, 431, 546, 281, 746, 513, 16, 179, 775, 133, 650, 827, 539, 715, 822, 529, 838, 105, 728, 351, 577, 660, 119, 873, 78, 530, 517, 56, 464, 615, 864, 581, 562, 403, 686, 165, 802, 406, 612, 820, 422, 133, 617, 816, 683, 483, 591, 92, 210, 787, 811, 249, 479, 264, 818, 479, 857, 367, 117, 708, 114, 386, 273, 865, 185, 139, 48, 189, 517, 864, 487, 323, 467, 451, 894, 235, 419, 350, 808, 124, 276, 743, 447, 659, 635, 38, 657, 641, 308, 465, 408, 177, 401, 21, 261, 524, 831, 537, 135, 496, 547, 61, 760, 446, 539, 892, 143, 425, 83, 585, 844, 9, 370, 387, 359, 268, 524, 747, 203, 679, 240, 448, 497, 646, 415, 882, 575, 385, 656, 674, 344, 695, 569, 736, 808, 377, 433, 527, 326, 632],
                 [11, 330, 659, 284, 380, 929, 579, 710, 470, 551, 957, 460, 371, 862, 88, 815, 337, 255, 754, 418, 604, 638, 509, 942, 481, 721, 181, 411, 617, 933, 351, 345, 890, 59, 539, 551, 760, 300, 393, 500, 316, 747, 414, 253, 556, 3, 537, 576, 416, 401, 51, 393, 281, 592, 507, 686, 682, 566, 7, 127, 264, 119, 935, 327, 173, 453, 742, 473, 541, 726, 451, 655, 352, 630, 513, 967, 822, 69, 40, 464, 450, 726, 848, 80, 274, 373, 374, 280, 919, 824, 900, 591, 764, 681, 962, 293, 394, 36, 327, 102, 514, 921, 619, 747, 942, 876, 64, 849, 384, 307, 140, 393, 500, 620, 169, 957, 877, 176, 231, 732, 254, 190, 167, 753, 153, 284, 13, 328, 118, 933, 826, 708, 899, 319, 761, 666, 609, 850, 882, 135, 120, 175, 63, 615, 658, 497, 716, 766, 616, 922, 964, 310, 671, 615, 391, 518, 994, 455, 571, 878, 991, 249, 620, 73, 84, 366, 865, 996, 442, 355, 223, 19, 740, 308, 477, 487, 91, 522, 197, 129, 635, 413, 275, 750, 53, 697, 876, 95, 547, 990, 620, 81, 457, 300, 164, 445, 305, 770, 7, 455, 576, 36, 625, 684, 598, 711, 889, 349, 458, 455, 85, 61, 225, 53, 335, 329, 32, 641, 205, 410, 135, 625, 494, 193, 565, 235, 803, 954, 271, 995, 599, 60, 981, 122, 793, 956, 185, 501, 901, 487, 190, 118, 313, 324, 199, 634, 774, 907, 101, 655, 637, 733, 425, 615, 106, 942, 464, 303, 797, 580, 255, 815, 513, 289, 702, 606, 947, 159, 89, 568, 563, 367, 493, 112, 498, 841, 341, 286, 386, 985, 60, 888, 290, 888, 140, 365, 442, 81, 94, 373, 816, 38, 197, 129, 92, 193, 224, 671, 480, 467, 793, 385, 930, 72, 561, 760, 174, 294, 490, 68, 451, 57, 354, 151, 29, 149, 0, 308, 647, 250, 184, 291, 70, 181, 96, 297, 381, 178, 753, 445, 826, 500, 631, 487, 343, 701, 715, 214, 238, 306, 157, 465, 824, 878, 609, 694, 593, 875, 682, 171, 781, 689, 968, 108, 754, 741, 751, 957, 430, 929, 411, 3, 0, 227, 126, 301, 673, 788, 847, 263, 117, 372, 98, 701, 297, 69, 931, 873, 952, 556, 999, 589, 238, 917, 159, 566, 689, 418, 837, 984, 621, 575, 240, 355, 994, 649, 256, 927, 20, 994, 415, 841, 216, 767, 690, 299, 64, 135, 632, 782, 483, 86, 821, 356, 226, 754, 92, 396, 186, 335, 343, 531, 958, 815, 602, 752, 117, 132, 969, 134, 761, 441, 905, 293, 851, 775, 807, 215, 238, 92, 684, 895, 77, 135, 764, 110, 418, 559, 513, 644, 815, 799, 618, 446, 359, 427, 778, 253, 741, 794, 323, 807, 29, 639, 301, 811, 109, 134, 666, 639, 525, 83, 230, 918, 360, 37, 969, 142, 742, 565, 100, 488, 3, 496, 858, 478, 876, 56, 177, 384, 976, 153, 700, 219, 864, 615, 845, 302, 387, 835, 537, 377, 991, 214, 719, 513, 583, 736, 94, 928, 89, 310, 229, 945, 858, 278, 272, 798, 555, 393, 759, 117, 875, 784, 777, 798, 559, 252, 444, 876, 101, 640, 95, 719, 146, 816, 406, 725, 260, 54, 930, 449, 204, 694, 319, 13, 113, 787, 91, 701, 989, 699, 911, 870, 328, 640, 968, 851, 446, 86, 484, 22, 551, 376, 38, 292, 929, 466, 453, 152, 616, 926, 2, 919, 523, 517, 386, 622, 372, 412, 485, 688, 90, 103, 947, 186, 401, 361, 766, 457, 269, 639, 157, 763, 516, 177, 270, 658, 452, 918],
                 [3194, 1213, 1020, 1739, 2568, 3365, 2682, 4839, 552, 1655, 338, 3860, 1516, 2718, 4429, 1972, 2842, 3343, 3318, 4275, 4813, 1695, 165, 2276, 4720, 3159, 930, 4926, 2262, 3387, 2949, 1709, 2427, 4068, 4550, 412, 1951, 3548, 3148, 1852, 3644, 4505, 654, 2985, 3126, 1539, 1578, 4867, 1111, 3252, 4295, 3094, 4433, 2634, 115, 4370, 2304, 1597, 2176, 483, 1041, 1185, 2060, 3195, 3730, 666, 583, 4861, 4214, 1443, 2218, 4081, 3169, 4075, 790, 4319, 3114, 2728, 133, 4874, 3568, 1348, 2935, 1533, 4424, 1036, 2924, 75, 239, 3606, 3924, 257, 420, 1485, 2113, 3740, 301, 4103, 1827, 4293, 1556, 3312, 4608, 2874, 4341, 3560, 3126, 626, 2347, 1529, 4244, 334, 1125, 3811, 1247, 1424, 2009, 2794, 4726, 3711, 3173, 1133, 394, 3242, 4501, 4336, 2823, 1527, 4133, 3534, 2471, 4248, 2548, 3486, 2788, 645, 4169, 3239, 4153, 2166, 2670, 1800, 4310, 1209, 2490, 3251, 2847, 1110, 1126, 2714, 3980, 4833, 1809, 813, 4439, 4308, 375, 4409, 1965, 129, 1978, 1890, 932, 1102, 2107, 1716, 290, 4538, 3413, 1386, 297, 2699, 4207, 1169, 1056, 4610, 1003, 756, 1913, 1139, 2554, 1685, 4079, 2302, 3690, 4288, 3395, 1768, 4211, 3187, 1760, 2210, 4181, 2494, 2688, 1001, 4305, 4175, 536, 4035, 380, 2581, 2794, 2479, 196, 4718, 2368, 2446, 4184, 1025, 3715, 2840, 2795, 921, 792, 1505, 592, 4016, 3070, 341, 3261, 2003, 2896, 1918, 1653, 953, 4104, 1662, 3837, 2306, 1954, 2322, 836, 2064, 2104, 2961, 321, 3256, 1320, 2882, 684, 4200, 1740, 793, 1826, 1410, 955, 2486, 4748, 902, 4886, 2604, 2146, 2839, 3676, 938, 2861, 2318, 1283, 1856, 2911, 3905, 1097, 1994, 2605, 2499, 4904, 3891, 88, 268, 897, 4393, 1418, 412, 3825, 2317, 1941, 3570, 4704, 1556, 2043, 3756, 1569, 1080, 503, 1658, 249, 4782, 3548, 3147, 2770, 1943, 3142, 3736, 693, 3103, 1181, 1334, 1029, 4242, 4528, 185, 3699, 487, 3259, 2534, 4482, 2109, 3027, 4935, 2421, 2983, 3887, 4324, 1543, 4274, 4386, 1364, 1951, 4801, 865, 728, 4868, 2065, 839, 1362, 4228, 2867, 3903, 929, 3137, 1446, 4614, 589, 955, 356, 3984, 4069, 89, 2020, 3277, 4369, 1044, 4657, 1367, 790, 1774, 552, 571, 1815, 630, 1057, 3937, 1330, 2279, 1449, 1827, 3959, 4594, 784, 750, 1052, 1877, 4037, 1473, 3174, 1682, 1511, 2878, 4534, 1522, 4489, 2133, 1885, 2213, 4003, 4422, 1610, 4161, 989, 643, 2049, 2437, 2718, 3032, 2493, 2718, 3479, 3984, 1257, 1035, 707, 2107, 121, 3897, 1142, 4078, 2064, 3997, 2522, 173, 2058, 4178, 2561, 2664, 3178, 921, 3087, 1975, 1664, 2445, 4850, 3620, 1045, 3464, 836, 1798, 1615, 1434, 1582, 1962, 3221, 1259, 3714, 2132, 4455, 2598, 4618, 954, 2921, 3581, 3814, 1351, 1583, 674, 1863, 214, 2811, 2727, 4895, 4670, 2658, 858, 2906, 2652, 4707, 962, 3401, 2514, 934, 674, 702, 383, 2470, 2890, 1479, 1239, 3505, 4544, 1982, 4169, 2974, 403, 1893, 3533, 378, 913, 1515, 1140, 2886, 936, 2882, 1153, 371, 1153, 4866, 4234, 539, 3748, 3512, 4796, 832, 3505, 1409, 448, 1166, 160, 3397, 4842, 322, 552, 1948, 2421, 784, 4583, 2432, 1570, 2917, 963, 1154, 907, 611, 4892, 3009, 889, 4370, 3131, 1858, 4961, 3048, 3431, 3004, 3467, 1282, 3257, 2592, 3587, 2454, 2414, 4744, 4940, 4492, 3414, 2336, 2820, 2398, 516, 3618, 2715, 4416, 1421, 373, 4612, 4034, 2335, 3925, 3420, 3197, 1274, 3569, 1309, 1498, 1141, 2699, 3357, 3606, 1416, 4327, 912, 2103, 3046, 2933, 1656, 332, 3378, 940, 2303, 3928, 4389, 3446, 1486, 3670, 211, 4882, 996, 3143, 745, 3336, 4662, 1105, 3969, 2603, 2521, 2926, 2078, 4642, 988, 1415, 3982, 3569, 2845, 4854, 3538, 1468, 1827, 1455, 3715, 3730, 1209, 1935, 4925, 673, 3831, 3642, 526, 4929, 586, 527, 561, 4900, 3506, 117, 4418, 2202, 1915, 1164, 2290, 2213, 175, 4915, 156, 3677, 2188, 2099, 1234, 410, 3961, 3523, 3615, 2864, 3394, 923, 3087, 1548, 4867, 820, 2809, 4611, 2984, 475, 619, 1104, 1244, 4100, 4082, 3056, 3079, 3224, 414, 3543, 2334, 3657, 2195, 4341, 2796, 334, 4360, 1331, 3673, 1946, 1962, 664, 1582, 1798, 2910, 3965, 3491, 3041, 357, 1186, 622, 792, 2145, 1767, 2744, 763, 817, 493, 2640, 3254, 3319, 4387, 4798, 3983, 1180, 1900, 925, 1608, 1433, 2827, 4981, 3420, 788, 1665, 4116, 572, 1617, 3759, 556, 4946, 3629, 2742, 1169, 2724, 2930, 242, 3543, 1372, 3040, 817, 1759, 3382, 959, 3602, 3468, 3292, 2359, 3372, 2745, 4430, 2121, 4271, 4616, 2433, 3650, 2761, 4150, 3123, 2069, 1656, 4056, 2814, 1057, 3797, 2016, 4930, 3550, 1426, 2254, 1189, 3878, 4874, 182, 1755, 195, 3647, 3617, 4460, 2364, 3844, 1673, 1831, 1736, 230, 2368, 2916, 222, 3254, 4255, 3058, 2155, 4815, 2336, 1367, 1910, 2005, 3940, 4384, 4932, 739, 860, 64, 4627, 2729, 4585, 1310, 3920, 4181, 3582, 4628, 2111, 1039, 3307, 3799, 708, 2065, 202, 4254, 2897, 219, 288, 4901, 4467, 4003, 2296, 2109, 4962, 3094, 4432, 381, 611, 680, 4877, 2827, 930, 905, 1820, 302, 3732, 2177],
                 [4265, 381, 1047, 3044, 2276, 1365, 407, 58, 2604, 4596, 1111, 3979, 1281, 4424, 4338, 2893, 1156, 376, 1976, 104, 4582, 546, 3864, 4663, 695, 1038, 1053, 2810, 4585, 1104, 1166, 4141, 2871, 3543, 3929, 3826, 2639, 4308, 4820, 1853, 3864, 3441, 3649, 4270, 2940, 727, 1705, 1318, 2423, 4504, 186, 973, 1894, 4398, 716, 52, 3618, 712, 2398, 1490, 2890, 3874, 2661, 1692, 4340, 3465, 1924, 3165, 4073, 4607, 2762, 637, 2141, 238, 1136, 2618, 4573, 192, 1783, 627, 4669, 4802, 969, 3183, 359, 2696, 4390, 1981, 3494, 671, 427, 2511, 3479, 4519, 812, 2270, 2775, 429, 3113, 4550, 4452, 904, 3122, 3936, 1076, 81, 747, 4790, 2895, 3509, 4337, 222, 142, 588, 4391, 3781, 1886, 3332, 4227, 4676, 1022, 3465, 2938, 2724, 1848, 432, 1625, 1829, 3676, 3592, 1305, 1822, 72, 2515, 4983, 1779, 726, 409, 744, 4246, 1877, 4580, 2280, 983, 2793, 1271, 3939, 3563, 1697, 3545, 399, 4881, 612, 1269, 3949, 424, 4607, 3395, 2215, 4593, 189, 3657, 3642, 3809, 219, 4157, 1496, 4269, 862, 3578, 1143, 2635, 3265, 2552, 3648, 3181, 3498, 945, 3963, 2741, 1498, 1047, 4474, 1342, 3776, 3204, 3631, 3455, 1378, 3755, 1098, 1227, 1094, 1832, 3420, 2430, 4569, 3424, 2762, 3008, 600, 4160, 4206, 4210, 2423, 1350, 2592, 4160, 3918, 4424, 4280, 1362, 600, 3866, 932, 4420, 4800, 463, 3152, 1404, 220, 1392, 4127, 2498, 4737, 3903, 1794, 4689, 4485, 1850, 2641, 4211, 4918, 4498, 3050, 4521, 3467, 1034, 2542, 3673, 4350, 4095, 4167, 1927, 857, 1454, 1257, 589, 4561, 424, 1818, 413, 2305, 1149, 2424, 3117, 4655, 4411, 780, 2274, 3201, 1942, 3490, 4678, 2241, 562, 3355, 970, 2377, 849, 3892, 4782, 2182, 3467, 4309, 4287, 652, 1010, 3732, 4045, 1740, 3808, 614, 3870, 1399, 2013, 2092, 2746, 2048, 1459, 1119, 4870, 2059, 3987, 3004, 2755, 3667, 1899, 1175, 4282, 487, 4145, 466, 1294, 1273, 2616, 2739, 876, 4450, 3932, 4374, 4328, 2455, 3862, 1324, 1230, 2455, 3696, 2913, 1963, 3279, 2903, 178, 4780, 2474, 737, 294, 4292, 1118, 1983, 4264, 322, 2345, 3615, 1124, 4309, 4465, 2507, 3040, 1180, 3237, 3556, 1007, 1865, 336, 67, 59, 1481, 2729, 4830, 621, 253, 490, 4509, 2170, 3078, 2296, 2853, 4902, 2385, 4661, 2225, 1700, 2101, 254, 4772, 3646, 4226, 1989, 334, 299, 1077, 4044, 180, 2655, 3732, 4357, 1715, 3189, 309, 1132, 1098, 2988, 2693, 4377, 3891, 924, 4976, 3721, 1200, 1663, 4890, 2472, 4830, 738, 3749, 2838, 2052, 1013, 4663, 1144, 2094, 4525, 794, 2423, 4657, 1021, 3648, 61, 990, 4336, 3950, 3442, 4789, 2823, 3466, 4449, 442, 4282, 4723, 3788, 2695, 13, 4153, 4626, 461, 858, 3207, 2389, 3250, 1587, 3677, 3353, 279, 4225, 3214, 609, 2548, 138, 3712, 4165, 4677, 1015, 3979, 2571, 4071, 2288, 2596, 670, 1572, 1630, 4761, 2497, 4258, 701, 1800, 3805, 3583, 4631, 3971, 4571, 883, 2599, 1643, 843, 53, 3671, 2594, 2932, 2462, 3619, 320, 3655, 3002, 4865, 1201, 3191, 3270, 571, 4487, 4090, 509, 2076, 1424, 4846, 1188, 3777, 1312, 277, 3124, 2543, 3961, 1074, 1700, 4828, 2070, 4971, 489, 3179, 879, 197, 2287, 1291, 551, 4422, 1767, 1000, 1531, 334, 1367, 128, 2118, 618, 559, 2551, 1310, 4332, 748, 4861, 460, 2863, 3521, 1748, 4818, 4010, 2815, 539, 2312, 1859, 2131, 787, 2795, 1686, 1473, 516, 4823, 4236, 3111, 898, 1172, 4816, 4955, 2142, 160, 2731, 1760, 1631, 1042, 862, 2115, 2311, 1812, 3371, 4850, 3169, 3124, 3038, 3927, 4815, 4206, 2491, 3606, 2532, 2727, 333, 2760, 3469, 2753, 4292, 1425, 3418, 3234, 3075, 3445, 2724, 4885, 2378, 2266, 1843, 3243, 2651, 3752, 761, 969, 2360, 1612, 1994, 2403, 1444, 4516, 4002, 3725, 3291, 3235, 1781, 2158, 3345, 42, 1988, 564, 4511, 4955, 4860, 1605, 4715, 191, 4722, 712, 3155, 3560, 4927, 4440, 3169, 4164, 163, 3931, 807, 3803, 1321, 3525, 55, 198, 4008, 568, 892, 3751, 1714, 4766, 4719, 77, 1271, 3410, 1490, 3432, 2218, 1910, 975, 3351, 2326, 3112, 3786, 4272, 4972, 76, 1111, 4336, 4196, 2870, 928, 978, 4592, 3505, 4430, 2629, 3629, 4295, 2276, 529, 3695, 57, 2575, 3533, 923, 2877, 3522, 4934, 1787, 805, 2832, 4594, 1993, 181, 3022, 169, 2997, 907, 4430, 2489, 2095, 1949, 1355, 2574, 1086, 4888, 4059, 2856, 4665, 3030, 4144, 3073, 1621, 1271, 2362, 2112, 886, 762, 768, 4905, 441, 1946, 853, 1653, 265, 195, 1902, 4453, 599, 2838, 1692, 3822, 270, 3292, 4260, 2942, 10, 4062, 3213, 4397, 1985, 2142, 298, 1628, 3401, 1185, 1042, 2606, 1395, 3659, 1834, 1708, 1003, 3549, 2792, 720, 3010, 3036, 3130, 556, 3558, 4677, 713, 3621, 1344, 2722, 3115, 1923, 4009, 1423, 1070, 2536, 1417, 2747, 170, 2761, 299, 4335, 4806, 746, 4586, 2038, 4342, 4301, 4941, 3989, 2864, 3569, 2089, 219, 2617, 1692, 4776, 1001, 1038, 488, 217, 3328, 2275, 85, 4714, 1857, 2795, 4744, 3000, 975, 141, 3249, 294, 3461, 747, 3078, 2856, 1451, 2821, 914, 4763, 2509, 4492, 1957, 2921, 615, 2170, 496, 2510, 4593, 1045, 4531, 877, 3701, 3589, 3771, 30, 4144, 1000, 1495, 3645, 334, 4973, 3564, 2622, 236, 2268, 3426, 3827, 2766, 190, 4067, 319, 1761, 2577, 3097, 3889, 2140, 2114, 1791, 27, 3760, 4244, 1352, 713, 2642, 1871, 3707, 958, 2463, 4325, 3253, 437, 3591, 4912, 850, 1630, 4813, 3748, 3678, 144, 3992, 3195, 3784, 2157, 3410, 3597, 3060, 2439, 1965, 1907, 3688, 121, 4439, 3218, 2467, 4837, 3518, 2286, 2610, 951, 1719, 114, 4264, 3951, 4936, 4002, 3848, 1437, 4074, 3733, 1971, 2680, 890, 3932, 3262, 2167, 1057, 589, 3376, 4112, 1980, 4592, 2463, 653, 1755, 4330, 519, 4279, 1618, 4986, 1232, 107, 1089, 1557, 844, 4844, 1988, 2876, 1167, 981, 1611, 4775, 152, 4743, 4051, 3352, 1821, 26, 51, 1173, 1232, 268, 2936, 1667, 1018, 4039, 2030, 1733, 3218, 4064, 3602, 2636, 1343, 1497, 362, 3955, 1703, 3691, 224, 1958, 3349, 2382, 627, 1626, 1558, 2869, 495, 1109, 3794, 3868, 1431, 2576, 129, 3891, 2348, 2843, 1013, 76, 3302, 4323, 1779, 1372, 1063, 3919, 25, 1507, 4578, 2587, 4286, 2353, 3297, 1277, 1295, 1960, 3967, 4976, 629, 125, 2011, 4391, 3405, 85, 549, 29, 1845, 425, 2651, 2516, 3842, 4309, 4884, 4053, 4250, 1661, 2744]]
    },
    'output': [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821]
}
In [13]:
test5 = {
    'input': {
        't':5,
        'n':[2,4,6,8,10],
        'prices':[[3,6],[3,5,2,9],[7,9,4,13,2,12],[0, 7, 5, 8, 6, 16, 8, 13],[13, 33, 15, 16, 18, 34, 37, 28, 2, 27]]
    },
    'output': [3, 17, 29, 59, 118]
}
In [14]:
test6 = {
    'input': {
        't':0,
        'n':[],
        'prices':[]
    },
    'output': "Error"
}
In [15]:
test7 = {
    'input': {
        't':1,
        'n':[1],
        'prices':[[10]]    
    },
    'output': [0]
}

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [16]:
tests = [test0,test1,test2,test3,test4,test5,test6,test7]
In [17]:
from jovian.pythondsa import evaluate_test_cases
In [ ]:
 
In [18]:
# add more test cases
In [ ]:
 

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. Come with a correct solution and explain it in simple words below:

  1. Initialize a python array full of zeros with length equal to the number of test cases
  2. Loop for all the test cases
  3. Initialize temporal variables for the number of days and the prices for each day for the current test
  4. Loop for all days and initialize a maxprice temp variable
  5. Loop from the current day of the outer loop for the number of the remaining days and find the current max of the subarray
  6. Update the profit by adding to the result the diffence between the price of the current day and the maxprice

Let's save and upload our work before continuing.

In [19]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project

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

In [20]:
def stockMax(t,n,prices):
    if t<1:
        return "Error"
    res=[0]*t
    for i in range(t):
        num_days=n[i]
        p=prices[i]
        for j in range(num_days):
            maxprice=0
            for k in range(j,num_days):
                if p[k]>maxprice:
                    maxprice=p[k]
            res[i]=res[i]+(maxprice - p[j])
    return res
In [ ]:
 
In [ ]:
 
In [ ]:
 

We can test the function by passing the input to it directly or by using the evaluate_test_case function from jovian.

In [21]:
from jovian.pythondsa import evaluate_test_case
In [22]:
evaluate_test_case(stockMax,test0)
Input: {'t': 3, 'n': [3, 3, 4], 'prices': [[5, 3, 2], [1, 2, 100], [1, 3, 1, 2]]} Expected Output: [0, 197, 3] Actual Output: [0, 197, 3] Execution Time: 0.014 ms Test Result: PASSED
Out[22]:
([0, 197, 3], True, 0.014)

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [23]:
from jovian.pythondsa import evaluate_test_cases
In [24]:
evaluate_test_cases(stockMax,tests)
TEST CASE #0 Input: {'t': 3, 'n': [3, 3, 4], 'prices': [[5, 3, 2], [1, 2, 100], [1, 3, 1, 2]]} Expected Output: [0, 197, 3] Actual Output: [0, 197, 3] Execution Time: 0.013 ms Test Result: PASSED TEST CASE #1 Input: {'t': 2, 'n': [4, 5], 'prices': [[1, 2, 3, 4], [5, 4, 3, 4, 5]]} Expected Output: [6, 4] Actual Output: [6, 4] Execution Time: 0.019 ms Test Result: PASSED TEST CASE #2 Input: {'t': 5, 'n': [10, 2, 6, 3, 4], 'prices': [[1, 10, 12, 8, 9, 17, 16, 11, 19, 17], [4, 7], [10, 13, 1... Expected Output: [68, 3, 28, 2, 4] Actual Output: [68, 3, 28, 2, 4] Execution Time: 0.034 ms Test Result: PASSED TEST CASE #3 Input: {'t': 2, 'n': [100, 500], 'prices': [[644, 1011, 1344, 1368, 870, 520, 367, 1864, 1319, 1751, 999, 1... Expected Output: [84172, 1234923] Actual Output: [84172, 1234923] Execution Time: 13.345 ms Test Result: PASSED TEST CASE #4 Input: {'t': 8, 'n': [50, 150, 200, 300, 500, 600, 800, 1000], 'prices': [[29, 20, 10, 18, 17, 15, 21, 25, ... Expected Output: [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821] Actual Output: [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821] Execution Time: 89.539 ms Test Result: PASSED TEST CASE #5 Input: {'t': 5, 'n': [2, 4, 6, 8, 10], 'prices': [[3, 6], [3, 5, 2, 9], [7, 9, 4, 13, 2, 12], [0, 7, 5, 8, ... Expected Output: [3, 17, 29, 59, 118] Actual Output: [3, 17, 29, 59, 118] Execution Time: 0.047 ms Test Result: PASSED TEST CASE #6 Input: {'t': 0, 'n': [], 'prices': []} Expected Output: Error Actual Output: Error Execution Time: 0.003 ms Test Result: PASSED TEST CASE #7 Input: {'t': 1, 'n': [1], 'prices': [[10]]} Expected Output: [0] Actual Output: [0] Execution Time: 0.006 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[24]:
[([0, 197, 3], True, 0.013),
 ([6, 4], True, 0.019),
 ([68, 3, 28, 2, 4], True, 0.034),
 ([84172, 1234923], True, 13.345),
 ([1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821],
  True,
  89.539),
 ([3, 17, 29, 59, 118], True, 0.047),
 ('Error', True, 0.003),
 ([0], True, 0.006)]

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In [25]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project
In [ ]:
 

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

In [26]:
# Time Complexity

'''
The worst-case time complexity is quadratic because for each day i we 
have a nested loop from i to N-1 to find the current maximum price
and decide when to sell to get maximum profit
'''
multiply_basic_time_complexity = 'O(n^2)'
In [27]:
# Space Complexity

'''
The worst-case space complexity is n because we need extra space to 
store the output for the t number of test cases and temporal variable 
to store the maxprice, number of days and predicted prices.

'''
multiply_basic_space_complexity = 'O(n)'
In [ ]:
 
In [28]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

We can reduce the time we need to find the profit and remove one of the inner loops as for N large the time increases quadratic. We can loop for every test case all the days of the current test case backward for all i from len(prices_of_current_test_case)-1 when i>-1 reducing in every step i by 1. We can then try and find the maximum of the backward array and update result.

In [ ]:
 
In [29]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project

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. Initialize a python array full of zeros with length equal to the number of test cases
  2. Loop for all the test cases
  3. Initialize temporal variables for the number of days and the prices for each day for the current test
  4. Implement a recursive function getMax()
  5. If number of days is less than or equal to zero then return output of profits
  6. Else check if current max is less than the current day price and update current max.
  7. Update the profit by adding to the result the diffence between the price of the current day and the maxprice and make a recursive call to the previous day

Let's save and upload our work before continuing.

In [30]:
jovian.commit()
[jovian] Attempting to save notebook.. [jovian] Updating notebook "vivipapa12/dsa-course-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/vivipapa12/dsa-course-project
In [ ]:
 
In [ ]:
 
In [ ]:
 

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

In [31]:
def getMax(p,i,curr_max,res):
    #print(p,i,curr_max,res)
    if i<0:
        return res
    else:
        if p[i]>curr_max:
            curr_max=p[i]
        res=res+(curr_max - p[i]) 
        return getMax(p,i-1,curr_max,res)
In [32]:
def stockMax_optimized(t,n,prices):
    if t<1:
        return "Error"
    res=[0]*t
    for i in range(t):
        num_days=n[i]
        p=prices[i]
        maxprice=0
        
        #for j in range(len(p)-1,-1,-1):
            
         #   if p[j]>=maxprice:
          #      maxprice=p[j]
        #res[i]=res[i]+(maxprice - p[j])
        res[i]=getMax(p,num_days-1,maxprice,res[i])
    return res
In [33]:
evaluate_test_cases(stockMax_optimized, tests)
TEST CASE #0 Input: {'t': 3, 'n': [3, 3, 4], 'prices': [[5, 3, 2], [1, 2, 100], [1, 3, 1, 2]]} Expected Output: [0, 197, 3] Actual Output: [0, 197, 3] Execution Time: 0.014 ms Test Result: PASSED TEST CASE #1 Input: {'t': 2, 'n': [4, 5], 'prices': [[1, 2, 3, 4], [5, 4, 3, 4, 5]]} Expected Output: [6, 4] Actual Output: [6, 4] Execution Time: 0.008 ms Test Result: PASSED TEST CASE #2 Input: {'t': 5, 'n': [10, 2, 6, 3, 4], 'prices': [[1, 10, 12, 8, 9, 17, 16, 11, 19, 17], [4, 7], [10, 13, 1... Expected Output: [68, 3, 28, 2, 4] Actual Output: [68, 3, 28, 2, 4] Execution Time: 0.013 ms Test Result: PASSED TEST CASE #3 Input: {'t': 2, 'n': [100, 500], 'prices': [[644, 1011, 1344, 1368, 870, 520, 367, 1864, 1319, 1751, 999, 1... Expected Output: [84172, 1234923] Actual Output: [84172, 1234923] Execution Time: 0.746 ms Test Result: PASSED TEST CASE #4 Input: {'t': 8, 'n': [50, 150, 200, 300, 500, 600, 800, 1000], 'prices': [[29, 20, 10, 18, 17, 15, 21, 25, ... Expected Output: [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821] Actual Output: [1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821] Execution Time: 1.242 ms Test Result: PASSED TEST CASE #5 Input: {'t': 5, 'n': [2, 4, 6, 8, 10], 'prices': [[3, 6], [3, 5, 2, 9], [7, 9, 4, 13, 2, 12], [0, 7, 5, 8, ... Expected Output: [3, 17, 29, 59, 118] Actual Output: [3, 17, 29, 59, 118] Execution Time: 0.016 ms Test Result: PASSED TEST CASE #6 Input: {'t': 0, 'n': [], 'prices': []} Expected Output: Error Actual Output: Error Execution Time: 0.002 ms Test Result: PASSED TEST CASE #7 Input: {'t': 1, 'n': [1], 'prices': [[10]]} Expected Output: [0] Actual Output: [0] Execution Time: 0.004 ms Test Result: PASSED SUMMARY TOTAL: 8, PASSED: 8, FAILED: 0
Out[33]:
[([0, 197, 3], True, 0.014),
 ([6, 4], True, 0.008),
 ([68, 3, 28, 2, 4], True, 0.013),
 ([84172, 1234923], True, 0.746),
 ([1322, 21266, 73644, 130620, 212690, 303955, 1984704, 2466821], True, 1.242),
 ([3, 17, 29, 59, 118], True, 0.016),
 ('Error', True, 0.002),
 ([0], True, 0.004)]
In [ ]:
 
In [ ]:
 

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

In [34]:
#Time complexity
'''
Since we have reduced the number of loops to only one backward traversal of all the array elements, finding the maximum
element and updating output, we have improved worst case time complexity to linear to the number of days we have predicted
the prices. So for large N the algorithm performs better.
'''

stockMax_optimized_time_complexity="O(n)"
In [35]:
#Space complexity
'''
Space complexity remains the same as above.
'''
stockMax_optimized_space_complexity="O(n)"
In [ ]:
 

If you found the problem on an external platform, you can make a submission to test your solution.

Share your approach and start a discussion on the Jovian forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

Submit Jovian Data Structures and Algorithms course project.

In [ ]:
jovian.submit(assignment="pythondsa-project")
[jovian] Attempting to save notebook..
In [ ]:
jovian.commit()
In [ ]: