[Swift]LeetCode152.乘积最大子序列|MaximumProductSubarray

OGeek|极客世界-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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
Explanation: [2,3] has the largest product 6.

Example 2:

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

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

12ms

 1 class Solution {
 2     func maxProduct(_ nums: [Int]) -> Int {
 3         guard nums.count > 0 else { return 0 }
 4         
 5         var minValue = nums[0], maxValue = nums[0], finalValue = nums[0]
 6         
 7         for i in 1..<nums.count {
 8             if nums[i] > 0 {
 9                 maxValue = max(nums[i], maxValue * nums[i])
10                 minValue = min(nums[i], minValue * nums[i])
11             }else {
12                 var tmp = maxValue
13                 maxValue = max(nums[i], minValue * nums[i])
14                 minValue = min(nums[i], tmp * nums[i])
15             }
16             finalValue = max(finalValue, maxValue)
17         }
18         
19         return finalValue
20     }
21 }

16ms

 1 class Solution {
 2     func maxProduct(_ nums: [Int]) -> Int {
 3         return getResult(nums)
 4     }
 5     
 6    private func getResult(_ array: [Int]) -> Int {
 7         var result = array[0]
 8         var previousMin = array[0]
 9         var previousMax = array[0]
10         var currentMin = array[0]
11         var currentMax = array[0]
12 
13         for el in array.dropFirst() {
14             currentMax = max(max(previousMax * el, previousMin * el), el)
15             currentMin = min(min(previousMax * el, previousMin * el), el)
16             result = max(currentMax, result)
17             previousMax = currentMax
18             previousMin = currentMin
19         }
20 
21         return result
22     }
23 }

28ms

 1 class Solution {
 2     func maxProduct(_ nums: [Int]) -> Int {
 3         guard !nums.isEmpty else { return 0 }
 4 
 5         var ret = nums.first!
 6         var (iMin, iMax) = (nums.first!, nums.first!)
 7 
 8         for n in nums.dropFirst() {
 9             if n < 0 {
10                 (iMin, iMax) = (iMax, iMin)
11             }
12 
13             iMin = min(n, iMin * n)
14             iMax = max(n, iMax * n)
15 
16             ret = max(ret, iMax)
17         }
18 
19         return ret
20     }
21 }

32ms

 1 class Solution {
 2 
 3     func maxProduct(_ nums: [Int]) -> Int {
 4         guard nums.count > 0 else {
 5             return 0
 6         }
 7         
 8         var minimum = 1
 9         var maximum = 1
10         var oldMax = maximum
11         var globalMax = nums[0]
12         
13         for num in nums {
14             if num < 0 {
15                 oldMax = maximum
16                 maximum = max(num, minimum*num)
17                 minimum = min(num, oldMax*num)
18             } else {
19                 maximum = max(num, maximum*num)
20                 minimum = min(num, minimum*num)
21             }
22             globalMax = max(globalMax, maximum)
23         }
24         
25         return globalMax
26     }
27 }

36ms

 1 class Solution {
 2     func maxProduct(_ nums: [Int]) -> Int {
 3         var lhs = 1
 4         var rhs = 1
 5         var maxhs = nums[0]
 6         
 7         for i in 0..<nums.count {
 8             lhs *= nums[i]
 9             rhs *= nums[nums.count - i - 1]
10             maxhs = max(maxhs, lhs, rhs)
11             
12             if lhs == 0 { lhs = 1}
13             if rhs == 0 { rhs = 1}
14             
15         }
16         return maxhs
17     }
18 }

40ms

 1 class Solution {
 2     func maxProduct(_ nums: [Int]) -> Int {
 3         guard nums.count > 0 else {
 4             return 0
 5         }
 6 
 7         var maxN = nums[0], maxT = 1, minT = 1
 8         for i in 0..<nums.count {
 9             let tmp1 = maxT * nums[i]
10             let tmp2 = minT * nums[i]
11             maxN = max(maxN, tmp1, tmp2)
12             maxT = max(tmp1, tmp2, 1)
13             minT = min(tmp1, tmp2, 1)
14         }
15         return maxN
16     }
17 }