LeetCode 152. Maximum Product Subarray

简介: 给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

v2-bba9b85eb1b87b5b2a6e5a2c074087db_1440w.jpg

Description



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] 不是子数组。


思路



  • 在一个连续的不含零的数组中,如果有偶数个负数,则最大值为所有值的乘积(所有的数都是整数,且不含零),如果有奇数个负数,为了取得最大值我们会尽可能使得序列包含更多的数,因此我们会舍弃第一个负数左边的序列或者最后一个负数右边的序列.
  • 基于这个思想,我们首先将给定的数组以0切片,切片的同时记录该片中负数的个数,然后求该片中的最大值,最后的结果为所有值的最大值.
  • 求每以片的最大值的过程是,如果有偶数个负数,则返回所有数的乘积;如果有奇数个乘积,我们首先找到第一个负数和最后一个负数,然后计算从第一个负数(不包含)到最后一个负数(不包含)中间的乘积middle,然后计算第一个负数(包含)左边的乘积left,计算最后一个负数(包含)右边的乘积right,返回middle*left,middle*right中的较大值.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-01-15 10:11:12
# @Last Modified by:   何睿
# @Last Modified time: 2019-01-15 12:37:11
from functools import reduce
class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res, count = nums[0], 0
        start, end = 0, 0
        for i in range(len(nums)):
            if nums[i] < 0:
                count += 1
            # 当遇到0或者到达末尾时就进行切片
            if nums[i] == 0 or i == len(nums) - 1:
                # 不包括元素num[i]本身
                end = i - 1 if nums[i] == 0 else i
                res = max(res, nums[i], self._product(start, end, count, nums))
                start, count = i + 1, 0
        return res
    def _product(self, start, end, count, nums):
        # 计算连续数字乘机最大值
        if start > end:
            return 0
        # 如果负数有偶数个,则所有值的连续相乘的积就是最大值
        if not count % 2:
            return reduce(lambda x, y: x * y, nums[start:end + 1])
        # 如果有奇数个负数,则我们应该丢掉第一个负数左边的片段或者最后一个负数右边的片段
        first, last = 0, 0
        # 寻找第一个负数的索引
        for i in range(start, end + 1):
            if nums[i] < 0:
                first = i
                break
        # 寻找最后一个负数的索引
        for i in range(end, start - 1, -1):
            if nums[i] < 0:
                last = i
                break
        # 如果第一个负数和最后一个负数不重合
        if first != last:
            # 计算从nums[first + 1:last]的乘机
            middle = reduce(lambda x, y: x * y, nums[first + 1:last])
            # 计算第一个负数左边的乘积(包括第一个负数本身)
            left = reduce(lambda x, y: x * y, nums[start:first + 1])
            # 计算最后一个负数右边的乘积(包括最后一个负数本身)
            right = reduce(lambda x, y: x * y, nums[last:end + 1])
        # 如果第一个负数和最后一个负数重合,即只有一个负数
        else:
            # 令中间的值为1
            middle = 1
            left = reduce(lambda x, y: x * y,nums[start:first]) if start != first else nums[start]
            right = reduce(lambda x, y: x * y,nums[last + 1:end + 1]) if last != end else nums[end]
        # 分别计算中间乘积与左边的乘积,中间乘积与右边的乘积
        res1, res2 = middle * left, middle * right
        # 返回最大值
        return res1 if res1 > res2 else res2


源代码文件在这里.


目录
相关文章
Leetcode 53.Maximum Subarray
题意简单,给出一个数组,求出其中最大的子数组和。 这种简单题目背后蕴藏着很巧妙的解题方法。其实只需要遍历一次数组就可以求得解。 思路是这样的,你想想看,如果一段子数组的和是负数, 那么这一段子数组不可能是最大和数组的一部分,丢掉重新从下一个位置开始选。
46 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
95 0
LeetCode 414. Third Maximum Number
LeetCode 318. Maximum Product of Word Lengths
给定一个字符串数组 words,找到 length(word[i]) * length(word[j]) 的最大值,并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词,返回 0。
77 0
LeetCode 318. Maximum Product of Word Lengths
LeetCode 239. Sliding Window Maximum
给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。 返回滑动窗口最大值。
63 0
LeetCode 239. Sliding Window Maximum
LeetCode 238. Product of Array Except Self
给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
86 0
LeetCode 238. Product of Array Except Self
LeetCode 209. Minimum Size Subarray Sum
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
116 0
LeetCode 209. Minimum Size Subarray Sum
LeetCode 164. Maximum Gap
给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。 如果数组元素个数小于 2,则返回 0。
80 0
LeetCode 164. Maximum Gap
LeetCode 104. Maximum Depth of Binary Tree
给定一颗二叉树,返回其最大深度. 注意:深度从1开始计数.
65 0
LeetCode 104. Maximum Depth of Binary Tree
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode contest 190 5417. 定长子串中元音的最大数目 Maximum Number of Vowels in a Substring of Given Length
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String
LeetCode Contest 186 5392. 分割字符串的最大得分 Maximum Score After Splitting a String