Problem statement

https://binarysearch.com/problems/Sublist-with-Largest-Min-Length-Product/

Solution

Equal to Leetcode 1793. Maximum Score of a Good Subarray.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, k):
        def test(nums, k):
            left  = list(accumulate(nums[:k+1][::-1], min))[::-1]
            right = list(accumulate(nums[k:], min))
            ans = -float("inf")
            for j in range(0, len(right)):
                i = bisect_left(left, right[j])
                if i >= 0: ans = max(ans, (k + j - i + 1) * right[j] )
            return ans

        return max(test(nums, k), test(nums[::-1], len(nums) - k - 1))

Remark

Notice, that there is also O(n) time complexity algorithm, where we use two pointers approach.