Leetcode 152 Maximum Product Subarray

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

• Bu soruda bize bir liste veriliyor.Ve listede çarpımları en yüksek olabilecek şekilde bir altkümenin çarpım sonucunu soruyor.
• Tüm sayılar pozitif olsa listenin kendisini dönerdik ama liste içindeki negatif sayılar işi bozuyor.
• Yapmamız gereken şey her önceki küme için hem minimum çarpıım hem de maksimum çarpımı elimizde tutarak ilerlemek.
• Bunun nedeni eğer listedeki bir sonraki sayı pozitif ise maximum çarpanı çarparak ilerleriz ama bir sonraki sayı negatif ise elimizdeki pozitif maksimum çarpmamız bize en yüksek sayıyı vermez aksine elimizdeki minimum negatif ise negatiflerin çarpımı pozitifi verir.
• Elimizdeki liste [2,3,-2] olsun. Bunun maksimum çarpanı 23 = 6 dır minimum çarpanı ise 3(-2) = -6 dır.
• Şimdi eğer listede bir adım ilerlersek [2,3,-2,4] elimize 4 gelir. Bu durumda [2,3,-2] listenin max = 6 idi 4 ile çarparız 24 buluruz.Peki eğer liste [2,3,-2,-4] olsaydı işte o zaman çarpacağımız negatif olacağı için önceki listenin min olan -6 ile çarpımı -6 * -4 = 24 bize maksimumu verirdi.

    def maxProduct(self, nums: List[int]) -> int:
        res = max(nums)
        curMin, curMax = 1, 1
        
        for n in nums:
            tmp=curMax * n
            curMax = max(n * curMax,n * curMin, n)
            curMin = min(tmp, n * curMin, n)
            res = max(res,curMax)
        return res