LeetCode - 152. Maximum Product Subarray

題目: 152. Maximum Product Subarray

給定一個整數陣列 `nums`，找出一個子陣列，使得其元素相乘的積最大，並回傳此最大積。
所有測試案例都保證答案在32位元整數的範圍內。

解題思路

可以使用一個變數currentProduct來記錄當前的子陣列元素積
以及一個變數 `maxProduct` 來記錄迄今為止找到的最大子陣列元素積。
接下來，遍歷整個陣列，並在每個元素上更新這兩個變數。

對於每個元素，可以將其乘到currentProduct上，
並將maxProduct與currentProduct比較取最大值。
如果currentProduct變為了 0，表示之前的元素積已經失去了意義，需要重置currentProduct為 1。

最後，需要從陣列的末尾開始再遍歷一次，因為有些最大積可能是由負數元素構成的。
在這次遍歷中，可以使用和前一次遍歷相同的方法來計算每個子陣列的元素積並更新maxProduct。

最後，只需要回傳maxProduct即可。

這個方法的時間複雜度是 $O(n)$，其中 $n$ 是陣列的長度，空間複雜度是 $O(1)$。

Code

Java:

Runtime 1 ms(87.54%), Memory 43.1 MB(11.48%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    public int maxProduct(int[] nums) {
        int current_product = 1;
        int max_product = Integer.MIN_VALUE;
        for(int i=0; i<nums.length; i++){
            current_product *= nums[i];
            max_product = Math.max(current_product, max_product);
            if(current_product == 0){
                current_product = 1;
            }
        }
        
        current_product = 1;
        for(int i=nums.length - 1; i>=0; i--){
            current_product *= nums[i];
            max_product = Math.max(current_product, max_product);
            if(current_product == 0){
                current_product = 1;
            }
        }
        return max_product;
    }
}

Python3:

Runtime 86 ms(67.6%), Memory 16.8 MB(11.23%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


import sys

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        current_product = 1
        max_product = -sys.maxsize - 1
        for i in range(len(nums)):
            current_product *= nums[i]
            max_product = max(max_product, current_product)
            if current_product == 0:
                current_product = 1

        current_product = 1
        for i in range(len(nums)-1, -1, -1):
            current_product *= nums[i]
            max_product = max(max_product, current_product)
            if current_product == 0:
                current_product = 1
        return max_product

C#:

Runtime 88 ms(74.46%), Memory 40.3 MB(31.52%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public class Solution {
    public int MaxProduct(int[] nums) {
        int current_product = 1;
        int max_product = int.MinValue;
        for(int i=0; i<nums.Length; i++){
            current_product *= nums[i];
            max_product = Math.Max(current_product, max_product);
            if(current_product == 0){
                current_product = 1;
            }
        }
        
        current_product = 1;
        for(int i=nums.Length - 1; i>=0; i--){
            current_product *= nums[i];
            max_product = Math.Max(current_product, max_product);
            if(current_product == 0){
                current_product = 1;
            }
        }
        return max_product;
    }
}

Golang:

Runtime 4 ms(88.15%), Memory 3.4 MB(99.45%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func maxProduct(nums []int) int {
    currentProduct := 1
    maxProduct := math.MinInt32
    for i := 0; i < len(nums); i++ {
        currentProduct *= nums[i]
        maxProduct = max(currentProduct, maxProduct)
        if currentProduct == 0 {
            currentProduct = 1
        }
    }

    currentProduct = 1
    for i := len(nums) - 1; i >= 0; i-- {
        currentProduct *= nums[i]
        maxProduct = max(currentProduct, maxProduct)
        if currentProduct == 0 {
            currentProduct = 1
        }
    }
    return maxProduct
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

C++:

Runtime 15 ms(10.35%), Memory 13.7 MB(86.21%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <algorithm>

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int currentProduct = 1;
        int maxProduct = INT_MIN;
        for(int i=0; i<nums.size(); i++){
            currentProduct *= nums[i];
            maxProduct = std::max(currentProduct, maxProduct);
            if(currentProduct == 0){
                currentProduct = 1;
            }
        }
        
        currentProduct = 1;
        for(int i=nums.size() - 1; i>=0; i--){
            currentProduct *= nums[i];
            maxProduct = std::max(currentProduct, maxProduct);
            if(currentProduct == 0){
                currentProduct = 1;
            }
        }
        return maxProduct;
    }
};

C:

Runtime 7 ms(69.93%), Memory 6.7 MB(44.76%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int maxProduct(int* nums, int numsSize) {
    int currentProduct = 1;
    int maxProduct = INT_MIN;
    for(int i = 0; i < numsSize; i++){
        currentProduct *= nums[i];
        maxProduct = max(currentProduct, maxProduct);
        if(currentProduct == 0){
            currentProduct = 1;
        }
    }
    
    currentProduct = 1;
    for(int i = numsSize - 1; i >= 0; i--){
        currentProduct *= nums[i];
        maxProduct = max(currentProduct, maxProduct);
        if(currentProduct == 0){
            currentProduct = 1;
        }
    }
    return maxProduct;
}