[Swift]LeetCode152. 乘积最大子序列 | Maximum Product Subarray
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 }