博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
152 Maximum Product Subarray
阅读量:6441 次
发布时间:2019-06-23

本文共 2876 字,大约阅读时间需要 9 分钟。

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.

刚看完覃超的直播。他说先不要用野路子dp,先老实开辟一个维度。 这题为什么要开辟一个新维度呢,因为这题要维护上一个最优值是max positive和min negtive两种情况。

public class Solution {    //dp[index][正负]    //dp[i][0] = dp[i-1][0] * nums[i] (nums[i]>=0)    or    dp[i-1][1] * nums[i](nums[i]<0)    //dp[i][1] = dp[i-1][1] * nums[i] (nums[i]>=0)    or    dp[i-1][0] * nums[i](nums[i]<0)    public int maxProduct(int[] nums) {        if (nums.length==0) return 0;        int dp[][] = new int[nums.length][2];        dp[0][0] = nums[0];        dp[0][1] = nums[0];        int res = nums[0] ;        for (int i = 1; i < nums.length; i++) {            if (nums[i] >= 0) {                dp[i][0] = dp[i - 1][0] * nums[i];                dp[i][1] = dp[i - 1][1] * nums[i];            } else {                dp[i][0] = dp[i - 1][1] * nums[i];                dp[i][1] = dp[i - 1][0] * nums[i];            }            dp[i][0] = Math.max(dp[i][0] , nums[i]);            dp[i][1] = Math.min(dp[i][1] , nums[i]);            res = Math.max(res,dp[i][0]);        }        return res;    }}复制代码

他这种写法,理解起来并不简单。。同样涉及到local跟global的那种原理。至少我现在很晕,可能因为很困了。12点多了还在公司,日。这题还可以状态压缩。

对于这种dp,还是要找时间跟code ganker那种local global的「」(其实我觉得他那种也不算野路子,也是一种套路)都好好理一遍。


12/04/2017更新

刚才又看了一遍这个题,重新定义了一遍状态:

nums[i]>=0 : dpPos[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值 dpNeg[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值 nums[i]<0 : dpNeg[i] = dpPos[i-1] * nums[i] 这里dpPos只存放positive max的值 dpPos[i] = dpNeg[i-1] * nums[i] 这里dpMin只存放negative min的值

这个方程对应的解法,九章上有:http://www.jiuzhang.com/solutions/maximum-product-subarray/

用野路子的空间轮换做了一遍,没有分开两个数组,而是只用了max min两个变量存储:

public int maxProduct(int[] nums) {        if (nums.length == 0) return 0;        int res = nums[0];        int maxPos = nums[0];        int minNeg = nums[0];        for (int i = 1; i < nums.length; i++) {            if (nums[i] >= 0) {                maxPos = maxPos * nums[i];                minNeg = minNeg * nums[i];            } else {                int minNegCopy = minNeg;                minNeg = maxPos * nums[i];                maxPos = minNegCopy * nums[i];            }            maxPos = Math.max(maxPos, nums[i]);            minNeg = Math.min(minNeg, nums[i]);            res = Math.max(maxPos, res);        }        return res;    }复制代码

这里注意那个Math.max在比较maxPos和minNeg的时候也要跟当前数字对比,我一开始不懂,后来了解到因为如果给这两个变量都初始化nums[0]的话,这样做就有道理了。还有,由于没有采用数组,这里需要创建一个minNegCopy。

code ganker的 local global解法:

public int maxProduct(int[] A) {    if(A==null || A.length==0)        return 0;    if(A.length == 1)        return A[0];    int max_local = A[0];    int min_local = A[0];    int global = A[0];    for(int i=1;i

他这边都没有判断nums[i]正负了,而是把三个数一起比较,很聪明。

转载于:https://juejin.im/post/5a31340cf265da43322792c9

你可能感兴趣的文章
zabbix监控tengine upstream状态
查看>>
mysql-binlog日志恢复数据库
查看>>
python之使用单元测试框架unittest执行自动化测试
查看>>
day10-多进程的基本语法
查看>>
凡客和锤子
查看>>
设计模式(5)--单例模式
查看>>
VS2015 RTM与ASP.NET 5 RC1之坑
查看>>
pitch yaw roll是什么
查看>>
python生成器 Generator
查看>>
Daily scrum[2013.12.09]
查看>>
深浅copy
查看>>
网络osi
查看>>
WINREG.H 编译出错
查看>>
Detours的使用准备
查看>>
xfs 文件系统损坏修复 fscheck
查看>>
Hibernate之一级缓存
查看>>
Python基础之定义有默认参数的函数
查看>>
443. String Compression - Easy
查看>>
Unity中那些事半功倍的好插件
查看>>
npm i 的几种方式区别
查看>>