# python – Finding the maximum profit [Optimization]

I am trying to optimize this as best as I can. Here are two possible solutions I have developed and their respective time and space complexity.

Can you please let me know if my time/space complexity is correct, and if there is a more optimized solution?

Problem:

Clear explanation:
https://aonecode.com/aplusplus/interviewctrl/getInterview/87934981990

My explanation:

There are a list of product stocks (4, 5, 3) which means there are 3
products, item 1 has 4 in stock, item 2 has 5 in stock, and item 3 has
3 in stock.

The profit on a single sale is the number of items left. When we make
a sale, we decrease the stock for that particular item.

For example, if we sell item 2, we make a profit of 5. The next time
we sell item 2, we make a profit of 4. Next time is 3.

We are told how many orders we can make, and we need to maximize the
profit within that order amount.

Example: items: (3, 4) orders: 6

Explanation: Prices are (4, 3, 2, 1) and (3, 2, 1). We sell
4+3+3+2+2+1

Python Heap solution. Time complexity: O(nlog(n)), Space complexity: O(n)

``````import heapq
def highestProfit(numSuppliers, inventory, order):
def pushHeap(heap, value):
heapq.heappush(heap, -1 * value)

def popHeap(heap):
return -1 * heapq.heappop(heap)

heap = ()
for i in inventory:
pushHeap(heap, i)

profit = 0
while (order > 0):
maxPrice = popHeap(heap)
profit += maxPrice
if (maxPrice - 1 != 0):
pushHeap(heap, maxPrice - 1)

order -= 1
return profit
``````

Non heap solution. Time complexity: O(n), Space complexity: O(n)

``````def highestProfitSimplified(numSuppliers, inventory, order):
maxInv = max(inventory)

arr = (0) * (maxInv + 1)
for i in inventory:
arr(i) += 1

print(arr)
profit = 0
while (maxInv >= 1 and order > 0):
profit += min(arr(maxInv), order) * maxInv

arr(maxInv - 1) += arr(maxInv)
order -= arr(maxInv)
maxInv -= 1

return profit
``````

Posted on Categories Articles