arraylist - Max product of a sublist of a list in python - Stack Overflow

admin管理员组

文章数量:1333476

This image contains Question Sorry can't provide in text as it can not be copy from the platform enter image description here

This is what I tried Test cases I was Having Problem solving Test case 2 all others worked fine with this code as you can see, I have hard coded the answer for test case 2.

am I doing something wrong? is there an alternate way to solve the question

This image contains Question Sorry can't provide in text as it can not be copy from the platform enter image description here

This is what I tried Test cases I was Having Problem solving Test case 2 all others worked fine with this code as you can see, I have hard coded the answer for test case 2.

am I doing something wrong? is there an alternate way to solve the question

• python
• arraylist

Share Improve this question Follow asked Nov 20, 2024 at 15:13 Tanishq UppalTanishq Uppal 9 6

• 1 I will solve after one hour because I am suspecting you are giving some kind of test – Anubhav Sharma Commented Nov 20, 2024 at 15:15
• 4 Please do not upload images of code/data/errors. – matszwecja Commented Nov 20, 2024 at 15:17
• is your test case 2 about max product as in image 1 or min product as in your code?(we can help your ocr your images, but first be clear in your question) – redoc Commented Nov 20, 2024 at 15:21
• 1 Proper handling of negative list elements is a bit tricky based on the list having an even or odd numer of negative items. – JonSG Commented Nov 20, 2024 at 15:23
• The question you linked mentions maxProduct and zero or positive integers. The code/test cases you linked feature minProduct and negative integers. Please fix this discrepancy. As for Test Case 2, in your code you only calculate products of sublists starting from l[0], so you'll never work on the [3, 5] sublist. – Swifty Commented Nov 20, 2024 at 15:44

 |  Show 1 more comment

1 Answer 1

Sorted by: Reset to default 1

Your method is O(n^2) time complexity. You allocate space for subarrays during each iteration with a space complexity of O(n).

Secondly, it is almost not worth mentioning the fact you hard coded a test case, this is of course not correct as you mention.

Solution:

Dynamically track the maximum and minimum product at every position in the list with one iteration.

Maintain a max_product and min_product value, the min_product is needed as multiplying a negative number by a negative min_produt will result in a maximum product.

Maintain a global_max value, update it to store the max product found so far in array.

If the current number is negative you swap the max_product and min_product as a negative number will have an opposite effect on a positive.

class Solution:
    def maxProduct(self, nums):
        if not nums:
            return 0
        
        max_product = nums[0]
        min_product = nums[0]
        global_max = nums[0]
        
        for i in range(1, len(nums)):
            num = nums[i]
            
            if num < 0:
                max_product, min_product = min_product, max_product
            
            max_product = max(num, max_product * num)
            min_product = min(num, min_product * num)
            
            global_max = max(global_max, max_product)
        
        return 2 * global_max

This solution has a time complexity of O(n) as it loops over once. The space complexity is O(1) as we only store the max and min values.

Your test cases:

# Test Case 1
print(sol.maxProduct([5, 2, 1, 1]))  # Expected Output: 20

# Test Case 2
print(sol.maxProduct([2, -2, 3, 5])) # Expected Output: 30

# Test Case 3 (Hidden Test Case)
print(sol.maxProduct([22, 11, 2, 2, 2, 1, 1, 1, 1, 0, 0,0, 1, 1, 3]))  # Expected Output: 3872

# Test Case 4 (Hidden Test Case)
print(sol.maxProduct([6, 6, 3, 3,34, 4, 4, 1, 0, 0, 1, 1]))  # Expected Output: 352512

# Test Case 5 (Hidden Test Case)
print(sol.maxProduct([2, 4, 3, 1, 2, 2, 3]))  # Expected Output: 576

Output:

20
30
3872
352512
576

Also, this is a relatively famous LeetCode question (with some changes), I remember solving this on a train.

本文标签： arraylistMax product of a sublist of a list in pythonStack Overflow