Skip to content

Instantly share code, notes, and snippets.

@tkausch
Created November 2, 2020 13:00
Show Gist options
  • Save tkausch/e263c9cbda4a7652df2543e36a84df32 to your computer and use it in GitHub Desktop.
Save tkausch/e263c9cbda4a7652df2543e36a84df32 to your computer and use it in GitHub Desktop.
Maximum Product Subarray problem
func maxProduct(_ nums: [Int]) -> Int {
guard nums.count > 0 else {
return 0
}
guard let first = nums.first, first != 0 else {
return max(0,maxProduct(Array(nums.dropFirst())))
}
var productMax = first
var productAll = first
var productUntilFirstNegativ: Int? = first < 0 ? Int.min : nil
for (i, num) in Array(nums.dropFirst()).enumerated() {
if num == 0 {
return max( maxProduct(Array(nums.dropFirst(i+2))), max(0, productMax))
} else{
productAll *= num
if let t = productUntilFirstNegativ {
productUntilFirstNegativ = (t == Int.min ? num : t * num)
} else {
productUntilFirstNegativ = num < 0 ? Int.min : nil
}
productMax = max(max(productAll, productUntilFirstNegativ ?? Int.min), productMax)
}
}
return productMax
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment