LeetCode/152_Maximum_Product_Subarray at master · KnowledgeCenterYoutube/LeetCode · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
Leetcode 152: Maximum Product Subarray
Detailed video Explanation: https://youtu.be/hJ_Uy2DzE08
=========================================


C++:
----
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max_overall = nums[0];
        int max_ending_here = nums[0], min_ending_here = nums[0];

        for(int i = 1; i < nums.size(); ++i){
            int tmp = max_ending_here;
            max_ending_here = max({nums[i], nums[i]*max_ending_here, nums[i]*min_ending_here});
            min_ending_here = min({nums[i], nums[i]*tmp, nums[i]*min_ending_here});
            max_overall = max(max_overall, max_ending_here);
        }
        return max_overall;
    }
};


Java:
-----
class Solution {
    public int maxProduct(int[] nums) {
        int max_overall = nums[0];
        int max_ending_here = nums[0], min_ending_here = nums[0];

        for(int i = 1; i < nums.length; ++i){
            int tmp = max_ending_here;
            max_ending_here = Math.max(nums[i], Math.max(nums[i]*max_ending_here, nums[i]*min_ending_here));
            min_ending_here = Math.min(nums[i], Math.min(nums[i]*tmp, nums[i]*min_ending_here));
            max_overall = Math.max(max_overall, max_ending_here);
        }
        return max_overall;
    }
}


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

        for i in range(1, len(nums)):
            tmp = max_ending_here
            max_ending_here = max({nums[i], nums[i]*max_ending_here, nums[i]*min_ending_here})
            min_ending_here = min({nums[i], nums[i]*tmp, nums[i]*min_ending_here})
            max_overall = max(max_overall, max_ending_here)

        return max_overall