leetcode152-乘积最大子数组

原题

给你一个整数数组 nums ,请你找出数组中乘积最大的连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

示例 1:

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

示例 2:

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

解法

思想

动态规划?正负之间的转换其实就是最大值和最小值之间的转换。

代码

class Solution {
    public int maxProduct(int[] nums) {
        int prevMin = nums[0], prevMax = nums[0], res = nums[0];
        int temp1 = 0, temp2 = 0;
        for (int i = 1; i < nums.length; i++) {
            temp1 = nums[i] * prevMax;
            temp2 = nums[i] * prevMin;
            prevMax = Math.max(Math.max(temp1, temp2), nums[i]);
            prevMin = Math.min(Math.min(temp1, temp2), nums[i]);
            res = Math.max(res, prevMax);
        }
        return res;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode152-%e4%b9%98%e7%a7%af%e6%9c%80%e5%a4%a7%e5%ad%90%e6%95%b0%e7%bb%84/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月17日
下一篇 2020年5月18日

相关推荐

  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0540
  • leetcode543-二叉树的直径

    原题 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例: 给定二叉树 1 / \ 2 3 / \ 4 5…

    算法 2020年3月10日
    0210
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0190
  • leetcode914-卡牌分组

    原题 给定一副牌,每张牌上都写着一个整数。 此时,你需要选定一个数字 X,使我们可以将整副牌按下述规则分成 1 组或更多组: 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。…

    算法 2020年3月27日
    090
  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->…

    算法 2020年6月16日
    01330
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01220
  • leetcode219-存在重复元素II

    原题 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。 示例1…

    算法 2019年12月24日
    0160
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    050
  • leetcode7-整数反转

    原题 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例1: 输入: 123 输出: 321 示例2: 输入: -123 输出: -321 示例3: 输…

    算法 2020年2月26日
    0110
  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0380

发表回复

登录后才能评论