pythonoptimizationtime-complexitycomplexity-theorydivide-and-conquer# Divide and Conquer max profit algorithm

I need to find a Divide and Conquer algorithm (for the max profit problem) with complexity `Θ(nlogn)`

but I am only able to find with complexity `Θ(n)`

.

The max profit problem is based on stocks. For example:

`array = [10, 4, 5, 2, 2, 2, 3, 1, 7, 10]`

Here you need to find the `max(A[j] - A[i])`

in the given array, but you need to have `j > i`

(as you cannot go back to time and buy the stock lets say the day it was created).So in this array the solution is `j = 8`

(the 8th element in the array) with `A[j] = 10`

and `i = 6`

.

My current code is

```
def find_max_profit_2(A, low, high):
if low > high:
return None
if low == high:
return low, low
middle = (low + high) // 2
j_a, i_a = find_max_profit_2(A, low, middle)
j_b, i_b = find_max_profit_2(A, middle + 1, high)
ret_j, ret_i = 0 , 0
if A[j_a] > A[j_b]:
ret_j = j_a
else:
ret_j = j_b
if A[i_a] < A[i_b]:
ret_i = i_a
else:
ret_i = i_b
return ret_j, ret_i
```

with `T(n) = 2T(n/2) + Θ(1)`

--> From Master Theorem case 1 the time complexity of my code is `T(n) = Θ(n).`

Remember the objective is to find a code with T(n) = Θ(nlogn)

Solution

It seems that to achieve a time complexity of `Θ(n log n)`

for the maximum profit problem using a divide and conquer approach we need to modify the algorithm so that each division step contributes more to the overall complexity than a simple `Θ(1)`

comparison.

Steps are:

- Divide the array into two halves (as you are already doing).
- Recursively find the maximum profit in each half. This is similar to your current approach.
- Find the maximum profit that crosses the midpoint. This step is crucial. It involves finding the maximum profit where the buying point is in the left half and the selling point is in the right half. This step should have a complexity of Θ(n) per division.

```
def find_max_profit_crossing(A, low, mid, high):
# Finding the minimum price in the left half
min_price = min(A[low:mid+1])
# Finding the maximum profit in the right half
max_profit = max([A[j] - min_price for j in range(mid+1, high+1)])
return max_profit
def find_max_profit(A, low, high):
if low == high:
return 0
mid = (low + high) // 2
# Maximum profit in left half
left_profit = find_max_profit(A, low, mid)
# Maximum profit in right half
right_profit = find_max_profit(A, mid + 1, high)
# Maximum profit crossing the midpoint
cross_profit = find_max_profit_crossing(A, low, mid, high)
return max(left_profit, right_profit, cross_profit)
```

So in this algorithm, each recursive call splits the problem in half (`Θ(log n)`

splits), and for each split, the `find_max_profit_crossing`

function computes the maximum profit that crosses the midpoint in linear time (`Θ(n)`

). Thus, the overall complexity becomes `Θ(n log n)`

, as per the Master Theorem for divide-and-conquer recurrences.

- Python Jinja2 LaTeX Table
- Getting attributes of a class
- How can I print many significant figures in Python?
- How to allow list append() method to return the new list
- Calculate Last Friday of Month in Pandas
- Python type hint for Iterable[str] that isn't str
- How to iterate over a list in chunks
- How to exit the entire application from a Python thread?
- Running shell command and capturing the output
- How do I pass a variable by reference?
- Convert range(r) to list of strings of length 2 in python
- How can I get the start and end dates for each week?
- how to use send_message() in python-telegram-bot
- Python conditional replacement based on element type
- How can I count the number of items in an arbitrary iterable (such as a generator)?
- Find longest consecutive range of numbers in list
- Insert text in braces with asyncpg
- How does one put a link / url to the web-site's home page in Django?
- How to determine if a path is a subdirectory of another?
- Custom Keybindings for Ipython terminal
- FastAPI asynchronous background tasks blocks other requests?
- How to make sure that information from one file is duplicated into several text documents, without specific lines
- Installing a Python environment with Anaconda
- sklearn pipeline model predicting same results for all input
- Brew command not found after installing Anaconda Python
- How to get an XPath from selenium webelement or from lxml?
- Pipe PuTTY console to Python script
- How to align the axes of a figure in matplotlib?
- Persist ParentDocumentRetriever of langchain
- How to reset index in a pandas dataframe?