`

LeetCode 152 - Maximum Product Subarray

 
阅读更多

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

 

public int maxProduct(int[] nums) {
    int result = nums[0];
    int minHere = nums[0], maxHere = nums[0];
    for(int i=1; i<nums.length; i++) {
        int a = minHere * nums[i];
        int b = maxHere * nums[i];
        maxHere = Math.max(Math.max(a, b), nums[i]);
        minHere = Math.min(Math.min(a, b), nums[i]);
        result = Math.max(result, maxHere);
    }
    return result;
}

 

分享到:
评论

相关推荐

    python-leetcode题解之152-Maximum-Product-Subarray.py

    代码示例中的Python-leetcode题解之152-Maximum-Product-Subarray.py,提供了一种简洁且高效的解决方案。通过简单的测试用例,可以验证代码的正确性。该题解为学习动态规划以及Python编程提供了很好的实践机会,并且...

    java-leetcode题解之Maximum Product Subarray.java

    在算法与编程的世界里,这类问题被称作“Maximum Product Subarray”(最大乘积子数组问题)。在LeetCode这个编程题库中,这个问题是被广泛研究和讨论的一个经典动态规划问题。本文将详细介绍如何使用Java语言解决...

    js-leetcode题解之152-maximum-product-subarray.js

    在解决LeetCode上的第152题“乘积最大子数组”时,JavaScript是一种常用的编程语言。该问题要求在给定的整数数组中找到一个连续子数组,使得这个子数组中所有数的乘积最大。为了解决这个问题,我们需要考虑数组中...

    leetcode和oj-leetcode-java:力扣在线裁判解决方案

    leetcode 和 oj LeetCode 解决方案 Java 版 Leetcode 问题分类 细绳 8 字符串到整数 ...oj_152_maximum_product_subarray / SRC /溶液/ oj_236_lowest_common_ancestor_of_bt / notes.md SRC /溶液/ oj

    leetcode写题闪退-LeetCode:leetcodeOJ

    leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...

    LeetCode最全代码

    318| [Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) | [C++](./C++/maximum-product-of-word-lengths.cpp) [Python](./Python/maximum-product-of-word-...

    Leetcode book刷题必备

    46. Maximum Product Subarray:找出一个数字序列中乘积最大的连续子序列。 47. Coins in a Line:n 个硬币排成一行,两个玩家轮流拿走左边或右边的一堆硬币,求得胜策略。 【二分搜索】 48. Search Insert ...

    leetcode二维数组搜索-leetcode:C中一些算法问题的解决

    leetcode二维数组搜索leetcode 对于 Leetcode ...最大积子./152_maximum_product_subarray.c ./9_palindrome_number.c : 回文数,O(1)空间复杂度 ./14_longest_common_prefix.c : 最长公共前缀 ./19_Remo

    interview:总结一下面试常考的算法题,希望可以帮助每一位想要提升自己面试能力的同学。对于每一道算法题会总结代码、时间复杂度以及一些好的blog

    对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)数组(...SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ClosestLeetCode 392 Is Subseq

    2018年最新Google Onsite面经总结1

    Maximum Product Subarray等。这类题目通常要求读者使用动态规划来解决问题,例如使用DP数组来记录状态、使用递归来计算结果等。 6. 排序和查找类题目 排序和查找类题目是LeetCode原题中的一个基础类题目,本文中...

    lrucacheleetcode-LeetCode_30Day:力扣30天挑战赛

    lru缓存leetcode 力扣_30天 力扣 30 天挑战赛 日 问题描述 问题和解决方案链接 Git 解决方案页面 1 SINGLE NUMBER 2 HAPPY NUMBER 3 MAXIMUM SUBARRAY 4 Move Zeroes 5 Best Time to Buy and Sell Stock II 6 GROUP ...

    3、动态规划必练题(含解法).pdf

    6. **Maximum Product Subarray** (最大乘积子数组) 类似于最大子数组和,但需要考虑负数的影响,可以同时维护最大正乘积和最大负乘积。 7. **Best Time to Buy and Sell Stock** 系列问题 股票买卖问题,涉及到...

    常见算法题答案及解析

    46. Maximum Product Subarray:计算子数组的最大乘积。 47. Coins in a Line:动态规划解决博弈问题,如Nim游戏。 八、二分查找 48. Search Insert Position:查找插入位置。 49. Find Minimum in Sorted Rotated ...

Global site tag (gtag.js) - Google Analytics