BinarySearch 0744 Cut Rods for Profit

Problem statement

https://binarysearch.com/problems/Cut-Rods-for-Profit/

Solution

For each length x we can decide if we want to cut each rod or not.

Complexity

It is O(n * m) for time and O(1) for space.

Code

class Solution:
    def solve(self, arr, P, C):
        if not arr: return 0
        ans = 0
        for x in range(1, max(arr) + 1):
            ans = max(ans, sum(max(0, a//x*P*x - (a-1)//x * C) for a in arr))
        return ans