During tough times like these, investment becomes more uncertain with more dangers. To solve it, we might try to train a model to decide when to buy or sell. Therefore, to provide it with correct data, we plan to design an algorithm that answers:what is the perfect moment to buy and when to sell to maximize your profit?Assume you must buyInput:???????: array listing ??????? ?? ??? ??????, where indices represent days; it has at least two valueschanges: array listing changes in the prices, where indices represent days; it has at least two valuesOutput:???????????:index of the change before which we buy:index of the change before which we sell:the profit of this intervali:index of the change before which we buyj:index of the change before which we sellmaxProfit:the profit of this intervalExample:Assume the below table contains the prices of a particular stock over days As we in general, try to solve the problem first; we start with a brute force, simple, algorithm: design it belowIn [ ]: # write your implementation heredef maxProfitBrute(changes):it returns the indices of (i,j) indicating the day to buy and sell respectivelyto have the maximum profit in a list of prices per day in .Inputs:- changes: the list holding the changes in prices; the value whose index is k representsthe change between day and day has at least a single change [two days]Output:i: the index of the change before which we buy- j: the index of the change after which we sell- maxProfit: the value of the maximum profitExample:changes = [1,2]that means the price started with ;- day 1: it became - day 2: it became In that case: (i,j) = (0,1) as we should buy at the first day, and sell after the third dayII II I# return the valuesreturn (0,0,0)In [ ]: # Try your algorithmmaxProfitBrute([13,7,-30,15,10,-5,12,7,-11,6])Divide and ConquerNow, we would try to use a divide and conquer paradigm. Hint: try the three steps, and design multiple versions to master these steps Input:changes : array listing changes in the prices, where indices represent days; it has at least two valuesOutput:i : index of the change before which we buyj: index of the change before which we sellmaxProfit : the profit of this intervalExample:Assume the below table contains the prices of a particular stock over dayspriceschangesDay Value506313270740-304551565106.60-577212879768-111074Therefore, the output of maxProfit([13,7,-30,15,10,-5,12,7,-11,6]) should be (3, 7, 39) .This is because our maximum profit would be 39when we buy the stock at day 4, index of 3, and sell after day 8, index of 7. Then, the total profit is 15 + 10 – 5 + 12 +7 = 39We will try to solve the problem using various techniques:• Brute-Force• Divide-and-Conquer

Answered: During tough times like these,…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

During tough times like these, investment becomes more uncertain with more dangers. To solve it, we might try to train a model to decide when to buy or sell. Therefore, to provide it with correct data, we plan to design an algorithm that answers:

what is the perfect moment to buy and when to sell to maximize your profit?
Assume you must buy

Input:

???????: array listing ??????? ?? ??? ??????, where indices represent days; it has at least two valueschanges: array listing changes in the prices, where indices represent days; it has at least two values

Output:

???????????:index of the change before which we buy:index of the change before which we sell:the profit of this intervali:index of the change before which we buyj:index of the change before which we sellmaxProfit:the profit of this interval

Example:
Assume the below table contains the prices of a particular stock over days

As we in general, try to solve the problem first; we start with a brute force, simple, algorithm: design it below
In [ ]: # write your implementation here
def maxProfitBrute(changes):
it returns the indices of (i,j) indicating the day to buy and sell respectively
to have the maximum profit in a list of prices per day in <changes>.
Inputs:
- changes: the list holding the changes in prices; the value whose index is k represents
the change between day <k> and day <k+1>
<changes> has at least a single change [two days]
Output:
i: the index of the change before which we buy
- j: the index of the change after which we sell
- maxProfit: the value of the maximum profit
Example:
changes = [1,2]
that means the price started with <x>;
- day 1: it became <x+1>
- day 2: it became <x+3>
In that case: (i,j) = (0,1) as we should buy at the first day, and sell after the third day
II II I
# return the values
return (0,0,0)
In [ ]: # Try your algorithm
maxProfitBrute([13,7,-30,15,10,-5,12,7,-11,6])
Divide and Conquer
Now, we would try to use a divide and conquer paradigm. Hint: try the three steps, and design multiple versions to master these steps

Input:
changes : array listing changes in the prices, where indices represent days; it has at least two values
Output:
i : index of the change before which we buy
j: index of the change before which we sell
maxProfit : the profit of this interval
Example:
Assume the below table contains the prices of a particular stock over days
prices
changes
Day Value
50
63
13
2
70
7
40
-30
4
55
15
65
10
6.
60
-5
7
72
12
8
79
7
68
-11
10
74
Therefore, the output of maxProfit([13,7,-30,15,10,-5,12,7,-11,6]) should be (3, 7, 39) .This is because our maximum profit would be 39
when we buy the stock at day 4, index of 3, and sell after day 8, index of 7. Then, the total profit is 15 + 10 – 5 + 12 +7 = 39
We will try to solve the problem using various techniques:
• Brute-Force
• Divide-and-Conquer

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions