1.(原文)问题描述
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.
2.翻译
找最大的数组中的子数组乘积 例如,给予的数组是[2,3,-2,4]
连续的字数组[2,3]有最大的乘积=6
3.解决思路分析
肯定可以通过其他方式实现就是不断的循环遍历,可是这样的代价太大,时间复杂度很高,我们j可以转换下思路好好想想如何最高效的来解决这个问题。
既然是求最大乘积那么我们需要考虑的就是最大乘积出现的情况可能有哪些:很显然有两种,第一种就是最大的累积乘以一个正数那么我们获取了更大的值,
还有就是一个最小的累积的值乘以一个负数,那么也可能获取的是最大的值,因为我们只需要保存乘积的最大和最小值。我们可以把数组的第一个值作为
最大最小值的逻辑值来处理,然后进行下去;如果之前的最大和最小值同当前元素相乘之后,没有当前元素大(或小)那么当前元素就可作为新的起点。
4.实现过程
Solution.java
package MaximumSubArray; public class Solution { public int maxProduct(int[] A) { if(A == null||A.length==0){
return 0;
}
int maxProduct = A[0]; //最大值的初始值
int maxTemp = A[0]; //累积的最大值
int minTemp = A[0]; //累积的最小值 for(int i = 1;i < A.length;i++) {//从数组的第二个元素开始遍历 int a = A[i]*maxTemp;
int b = A[i]*minTemp;
maxTemp = Math.max(Math.max(a,b), A[i]);//选取最大值的新起点
minTemp = Math.min(Math.min(a,b), A[i]);//选取最小值的新起点
maxProduct = Math.max(maxProduct, maxTemp);//更新最大值
}
return maxProduct;
} }
SolutionTest.java
package MaximumSubArray; public class SolutionTest { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub int []array1 = {0,2,3,5,6,8,0,9};
int []array2 = {1,-2,-3,-5,6,8,0,9};
int []array3 = {1,2,-3,5,6,8,0,9};
int []array4 = {1,2,0,5,6,8,0,9}; System.out.println(new Solution().maxProduct(array1));
System.out.println(new Solution().maxProduct(array2));
System.out.println(new Solution().maxProduct(array3));
System.out.println(new Solution().maxProduct(array4));
} }
5.有句话很正确,解决思路很重要,重要的是思想。
LeetCode之Maximum Product Subarray的更多相关文章
-
求连续最大子序列积 - leetcode. 152 Maximum Product Subarray
题目链接:Maximum Product Subarray solutions同步在github 题目很简单,给一个数组,求一个连续的子数组,使得数组元素之积最大.这是求连续最大子序列和的加强版,我们 ...
-
【LeetCode】Maximum Product Subarray 求连续子数组使其乘积最大
Add Date 2014-09-23 Maximum Product Subarray Find the contiguous subarray within an array (containin ...
-
[LeetCode] 152. Maximum Product Subarray 求最大子数组乘积
Given an integer array nums, find the contiguous subarray within an array (containing at least one n ...
-
LeetCode 152. Maximum Product Subarray (最大乘积子数组)
Find the contiguous subarray within an array (containing at least one number) which has the largest ...
-
[leetCode][001] Maximum Product Subarray
题目: Find the contiguous subarray within an array (containing at least one number) which has the larg ...
-
Java for LeetCode 152 Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest ...
-
leetcode 152. Maximum Product Subarray --------- java
Find the contiguous subarray within an array (containing at least one number) which has the largest ...
-
C#解leetcode 152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest ...
-
[leetcode]152. Maximum Product Subarray最大乘积子数组
Given an integer array nums, find the contiguous subarray within an array (containing at least one n ...
随机推荐
-
支付宝alipay使用小结 调用支付宝程序被杀死说明
一. 准备阶段 如果没有蚂蚁金服开放平台的注册账号,则需要实现注册一个,这里多说一点,就是当我们以公司名义注册账号时,需要预备公司的营业执照等物品(需要上传照片等信息审核).账号申请成功之后,我们需要 ...
-
LINQ for XML简单示例
LINQ,语言集成查询(Language Integrated Query)是一组用于c#和Visual Basic语言的扩展.它允许开发人员以与查询数据库相同的方式操作内存数据.从技术角度而言,LI ...
-
Javascript nextElementSibling和nextSibling
function next(ele) { if (typeof ele.nextElementSibling == 'object') { return ele.nextElementSibling; ...
-
HDU 4496 D-City (并查集)
题意:给定一个图,问你每次删除一条边后有几个连通块. 析:水题,就是并查集的运用,倒着推. 代码如下: #include <cstdio> #include <string> ...
-
最小日志量的insert操作
--1.实验环境 SQL> conn scott/tiger Connected to Oracle Database 11g Enterprise Edition Release 11.2.0 ...
-
Openjudge-NOI题库-蛇形填充数组
题目描述 Description 用数字1,2,3,4,...,n*n这n2个数蛇形填充规模为n*n的方阵. 蛇形填充方法为: 对于每一条左下-右上的斜线,从左上到右下依次编号1,2,...,2n-1 ...
-
javascript中关于this指向问题详解
前 言 LiuDaP 在前端的学习中,我们必然要用到js,js可以说是前端必不可少的的东西.在学习js的过程中,我们会经常用到this这个东西,而this的指向问题就变得尤为重要.今天正好有空闲 ...
-
edu9E. Thief in a Shop
题意:n个物品每个价值a[i],要求选k个,可以重复,问能取到哪几个价值 题解:fft裸题.但是直接一次fft,然后快速幂会boom.这样是严格的\(2^{20}*log2(2^{20})*log(w ...
-
linux chkconfig添加开机启动服务
--add:增加所指定的系统服务,让chkconfig指令得以管理它,并同时在系统启动的叙述文件内增加相关数据: --del:删除所指定的系统服务,不再由chkconfig指令管理,并同时在系统启动的 ...
-
javascript 获得以秒计的视频时长
<!DOCTYPE html> <html> <body> <h3>演示如何访问 VIDEO 元素</h3> <video id=&q ...