Max Product Vs Max Sum

Maximum Product Subarray vs Maximum Subarray (Kadane's Algorithm)

Maximum Subarray (Kadane's Algorithm)

We can use the following Kadane's algorithm

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sumMax = nums[0]

        currentSum = 0

        for num in nums:
            currentSum = max(currentSum + num, num)
            sumMax = max(sumMax, currentSum)
        
        return sumMax

Basically at 1 point we know that we can reset the sum to num if currentSum + num < num.

However this will not work for maxProduct.

Maximum Product Subarray

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

        currentProduct = 1

        for i in range(0, len(nums)):
            if currentProduct == 0:
                currentProduct = nums[i]
            else:
                currentProduct *= nums[i]
            
            maxProduct = max(maxProduct, currentProduct)

        currentProduct = 1
        for i in range(len(nums) - 1, -1, -1):
            if currentProduct == 0:
                currentProduct = nums[i]
            else:
                currentProduct *= nums[i]
            
            maxProduct = max(maxProduct, currentProduct)


        return maxProduct

For max product, we need to calculate the product from left -> right and from right -> left.

This is because if we follow the other method, we don't know what we should reset max product to. Since if it's negative but later on multiply by another negative it will still be a solution.

Maximum Sum Array can also follows the formular of Maximum Product Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sumMax = nums[0]

        total = 0

        for i in range(0, len(nums)):

            if (total + nums[i] < nums[i]): 
                total = nums[i]
            else:
                total += nums[i]

            sumMax = max(sumMax, total)
        
        total = 0

        for i in range(len(nums) - 1, -1, -1):

            if (total + nums[i] < nums[i]): 
                total = nums[i]
            else:
                total += nums[i]
            
            sumMax = max(sumMax, total)

        return sumMax

Same concept of calculating from left -> right and right -> left