Leetcode - Maximum Product Subarray

1331 ワード
dynamic programming leetcode algorithm DP テキストリンク
Leetcode : Maximum Product Subarray
Description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1
Input
[2,3,-2,4]
Output
6
Example 2
Input
[-2,0,-1]
Output
0
Approach
The presence of negative number and zero within the list can quickly change the values of maximum and minimum number. Hence, the program must compare every possible values - current, current * min, current * max
Solution (Python)
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxSub = nums[0]
        minSub = nums[0]
        result = nums[0]
        
        for i in range(1, len(nums)):
            curr = nums[i]
            
            tempMax = max(curr, maxSub * curr, minSub * curr)
            minSub = min(curr, maxSub * curr, minSub * curr)
            
            maxSub = tempMax
            
            result = max(maxSub, result)
        
        return result
MySQL inとexistsの最適化について
コード嗅覚91 -テストなしで断言する