LeetCode Maximum Product Subarray 解题报告

LeetCode Maximum Product Subarray 解题报告

大家好,又见面了,我是全栈君。

LeetCode 新题又更新了。求:最大子数组乘积。

https://oj.leetcode.com/problems/maximum-product-subarray/

题目分析:求一个数组,连续子数组的最大乘积。

解题思路:最简单的思路就是3重循环。求解productArray[i][j]的值(productArray[i][j]为A[i]到A[j]的乘积),然后记录当中最大值,算法时间复杂度O(n3)。必定TLE。

第一次优化,动态规划。求解:productArray[i][j]的时候不用再次循环从i到j。而是利用:productArray[i][j]=productArray[i][j-1]*A[j];採用递推的方法来计算,算法时间复杂度为O(n2),遗憾的是也TLE了。

public class Solution {
    public int maxProduct(int A[]) {
        if(A==null||A.length==0) {
	      return 0;
	    }
	    int[][] productArray =  new int[A.length][A.length];
	    int maxProduct = A[0];
	    
	    for(int i=0;i<A.length;i++) {
	    	for(int j=i;j<A.length;j++) {
	    		if(j==i) {
	    		    productArray[i][i] = A[i];
	    		} else {
	    		    productArray[i][j] = productArray[i][j-1]*A[j];
	    		}
	    		if(productArray[i][j]>maxProduct) {
	    			maxProduct = productArray[i][i];
	    		}
	    	}
	    }
	    return maxProduct;
    }
}

第二次优化。事实上子数组乘积最大值的可能性为:累乘的最大值碰到了一个正数;或者。累乘的最小值(负数),碰到了一个负数。所以每次要保存累乘的最大(正数)和最小值(负数)。同一时候另一个选择起点的逻辑。假设之前的最大和最小值同当前元素相乘之后,没有当前元素大(或小)那么当前元素就可作为新的起点。比如,前一个元素为0的情况,{1,0,9,2}。到9的时候9应该作为一个最大值,也就是新的起点。{1,0,-9,-2}也是相同道理,-9比当前最小值还小,所以更新为当前最小值。

这样的方法仅仅须要遍历一次数组就可以,算法时间复杂度为O(n)。

public class Solution {
    public int maxProduct(int A[]) {
        if(A==null||A.length==0) {
	      return 0;
	    }
	    int maxProduct = A[0];
	    int max_temp   = A[0];
	    int min_temp   = A[0];
	    
	    for(int i=1;i<A.length;i++) {
	    	int a = A[i]*max_temp;
	    	int b = A[i]*min_temp;
	    	max_temp = Math.max(Math.max(a,b), A[i]);
	    	min_temp = Math.min(Math.min(a,b), A[i]);
	    	maxProduct = Math.max(maxProduct, max_temp);
	    }
	    return maxProduct;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115679.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sql 2003错误 ERROR 2003: Can’t connect to MySQL server on ‘localhost’ (10061)

    sql 2003错误 ERROR 2003: Can’t connect to MySQL server on ‘localhost’ (10061)系统把你SQL停了,在键盘上的win+R键打开运行,输入services.msc打开服务面板找到SQL左上脚启动,再重启SQL,搞定。

  • js单项选择答题_完成窗口切换的方法

    js单项选择答题_完成窗口切换的方法业务背景:系统有一个数据列表,其中的每行数据都可以进行详细信息修改配置。为了提升用户体验,需要在用户触发单条任务记录详细配置界面之后添加进入上一题和下一题的操作。实现构思: 有两种办法:第一种简单点的话就是不去数据库实时查询数据,利用已经在列表中的数据信息进行数据切换展示与修改。 第二种办法稍微麻烦一点,数据切换的时候实时rownum去数据库查询定位当前数据行的index,然后切换…

  • java和c语言哪个简单_Java编程和C语言哪个好学

    java和c语言哪个简单_Java编程和C语言哪个好学学哪种编程语言好?计算机编程语言非常多,诸如Java、C、C++、PHP等,很多人在选择的时候都会觉得头大。到底学哪种编程语言好?很多人都拿Java和c相比较,那么今天小编就来先说说我的个人理解吧,学习Java很简单上手很容易,只需要会拼音就可以,简直而且没有门槛,而c语言学习成本高,要想学会需要投入较大的精力,才能有一个相对不错的回报。下面是Java和c的市场占有率,可以看出,二者不分伯仲,第一…

  • 第十七篇:实例分析(1)–初探WDDM驱动学习笔记(八)

    第十七篇:实例分析(1)–初探WDDM驱动学习笔记(八)

  • android 混淆不起作用,Android代码混淆的写法总结

    android 混淆不起作用,Android代码混淆的写法总结Apk文件被反编译出来能被获取到里面的代码。对于这种情况,我们可以对项目代码进行混淆,随机生成难理解的类名,方法名,让代码难以阅读,加大功能被盗取的难度。混淆可以起到压缩Apk,混淆文件,预检,优化的作用。1.使用方式,在gradle文件中设置minifyEnabled为true即可开启混淆buildTypes{release{minifyEnabledture//是否开启代码混淆pro…

  • accumulate

    accumulate

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号