# https://leetcode.com/problems/maximum-product-subarray/solution/
# Find start and ending indicies of maximum product subarray

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0

        max_so_far = nums[0]
        min_so_far = nums[0]
        result = max_so_far
        end_index = 0
        for i in range(1, len(nums)):
            curr = nums[i]
            temp_max = max(curr, max_so_far * curr, min_so_far * curr)
            min_so_far = min(curr, max_so_far * curr, min_so_far * curr)

            max_so_far = temp_max
            if max_so_far>result:
                result = max_so_far
                end_index = i

        cur = nums[end_index]
        j = end_index-1
        # no change in complexity
        while cur != result and j>=0:
            cur *= nums[j]
            j -= 1
        print(nums[j+1:i+1])
        return result