public class MaxProduct {
/**
* 编程之美 子数组的最大乘积
* 题目: 给定一个长度为N的整数数组,只允许使用乘法,不能用除法,计算任意N-1个数的组合中乘积中最大的一组,并写出算法的时间复杂度。
* 以下程序对应书上两种方法,求得“乘积中最大的一组”的乘积——都是有溢出的可能的。
* 但按题目的意思,是要求得这个子数组,而不是这个子数组的乘积。
* 实际应用中,返回去掉的那一个元素的下标更合理。
*/
private boolean invalidInput = false;
public static void main(String[] args) {
int[][] aa = {
{ 0, 0, 1, 2 },
{ 0, 1, 2 },
{ 0, -1, 2 },
{ -1, -2, -3 },
{ 1, 2, 3 },
};
for (int[] a : aa) {
MaxProduct m = new MaxProduct();
int result = m.maxProductA(a);
int result2 = m.maxProductB(a);
if (m.invalidInput) {
System.out.println("invalid input!");
} else {
System.out.println(result + "," + result2);
}
}
}
// 对应书上的解法1.空间换时间
public int maxProductA(int[] a) {
if (a == null || a.length == 0) {
invalidInput = true;
return 0;
}
int n = a.length;
int[] s = new int[n];
s[0] = 1;
for (int i = 1; i <= n - 1; i++) {
s[i] = s[i - 1] * a[i - 1];
}
int[] t = new int[n];
t[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
t[i] = t[i + 1] * a[i + 1];
}
int p = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int pi = s[i] * t[i];
if (pi > p) {
p = pi;
}
}
return p;
}
/*
对应书上的解法2。对乘积作分类讨论。书上的分析如下:
计算N个数的乘积为P,然后分P的正负性讨论如下:
1,P==0
说明P中必定至少含有一个0。假设将这个0去掉后得到N-1个元素的乘积为Q。
1.1 Q==0
返回0。说明N个元素中必有至少两个0,所以不管去掉什么元素,N-1个乘积必为0。
1.2 Q为正
返回Q。说明其中再无0了,若之前去掉的不是0,则剩余的N-1个的乘积必为0。小于现在的Q。
1.3 Q为负
返回0,。说明其中再无0了,若之前去掉的不是0,则剩余的N-1个的乘积必为0。大于现在的Q,取大者,所以之前应该保留0。
2,P为负
说明这N个数中无0,并且至少有一个负数。所以只有去掉一个绝对值最小的负数才获得最大乘积Q。并且这个负数必定是存在的。
3,P为正
由于可能负负得正,所以现在应该考虑到应该去掉一个绝对值最小的正数,但是这个正数不一定存在,比如数组-1,-1。所以如果该正数不存在,就应该去掉一个绝对值最大的负数。
同时注意,为了避免乘积溢出,建议只统计符号,计算0,正,负的个数 。
*/
public int maxProductB(int[] a) {
if (a == null || a.length == 0) {
invalidInput = true;
return 0;
}
int n = a.length;
int zeroCount = 0;
int negativeCount = 0;
int positiveCount = 0;
int maxNegative = Integer.MIN_VALUE; // 最大的负整数是-1,初始化应该设为最小的负整数
int minNegative = -1; // 最小的负整数是Integer.MIN_VALUE.,初始化应该设为最大的负整数
int minPositive = Integer.MAX_VALUE; // 最小的正整数,初始化为最大的正整数
for (int i : a) {
if (i == 0) {
zeroCount++;
}
if (i > 0) {
positiveCount++;
if (minPositive > i) {
minPositive = i;
}
}
if (i < 0) {
negativeCount++;
if (maxNegative < i) {
maxNegative = i;
}
if (minNegative > i) {
minNegative = i;
}
}
}
// 设P为数组所有元素的乘积。Q为除去一个0元素之外其他元素的乘积。
int p = 1;
int excludeItem = 0;
// P=0
if (zeroCount >= 2) { // 有两个或两个以上的0
p = 0;
} else if (zeroCount == 1) { // 有一个0
if (negativeCount % 2 == 0) { // Q>0
excludeItem = 0;
} else { // Q<0
p = 0;
}
} else {
// P>0
if (negativeCount % 2 == 0) {
if (positiveCount > 0) {
excludeItem = minPositive;
} else {
excludeItem = minNegative;
}
//P<0
} else {
excludeItem = maxNegative;
}
}
if (p != 0) {
for (int i = 0; i < n; i++) {
if (excludeItem != a[i]) {
p *= a[i];
}
}
}
return p;
}
}
分享到:
相关推荐
最大乘积子阵列(中) - 除自身以外的数组的乘积(中) - 查找数组中的所有重复项(中) - 移零(简单) - 数组的度数(简单) - 两和(简单) - 最大子阵列(简单) - 买卖股票的最佳时机(简单) - 包含重复(简单...
学生好用的 代码,计算机体系结构实验课需要的代码,求2个二维数组积
编程输入两个n阶下半三角矩阵,输出这两个矩阵的乘积。要求n阶下半三角矩阵采用一维数组压缩存储(即只存储下半三角)。 程序先从键盘(或字符文件)输入n值,建立三个矩阵的一维数组动态存储结构,然后从键盘(或字符...
o 2.2 寻找和为定值的两个数 o 2.3 寻找和为定值的多个数 o 2.4 最大连续子数组和 o 2.5 跳台阶 o 2.6 奇偶排序 o 2.7 荷兰国旗 o 2.8 矩阵相乘 o 2.9 完美洗牌 o 2.15 本章习题 第三章 树 o 3.0 本章导读 o 3.1 ...
最大产品子数组-https: 搜索最小值在旋转的数组排序- 搜索在旋转的数组排序- 3Sum- //leetcode.com/problems/3sum/ 盛满水的容器-https: 二元 两个整数之和-https: 1位数量-https: 计数位数-https: ...
| |进度| |数组| | 两次和-https: 最佳买卖股票时间-https: 包含重复-https: 阵列除自身之外的乘积-https: 最大子数组-https: 最大产品子数组-https: 搜索最小值在旋转的数组排序- 搜索在旋转的数组排序- 3Sum- //...
3.4 译码、布尔显示数字 要显示数字时,只需将数字乘以7,再将乘积的值作为索引在那存放真值的数组里寻找对 应显示的七个布尔显示控件的值。如显示'2',则从数组的第2*7=14位开始,依次取出7 个(分别代表着七个...
2、用公式求和、求乘积-11 6 3、字符串字符数组-12 16 4、一维数组-3 27 5、二维数组-7 29 6、数的拆分-3 36 7、素数-2 38 8、最大公约数,最小公倍数-6 39 9、其他-1 44 《C语言程序设计》复习纲要 1、 考试题型...
在排序数组中查找数字.py 二叉搜索树的第k大节点.py 二叉树的深度.py 数组中数字出现的次数.py 和为s的数字.py 翻转字符串.py ...构建乘积数组.py 把字符串转换成整数.py 树中两个节点的最低公共祖先.py
王知昆 -《浅谈用极大化思想解决最大子矩形问题》 伍 昱 -《由对称性解2-SAT问题》 项荣璟 -《充分利用问题性质——例析动态规划的"个性化"优化》 许智磊 -《浅谈补集转化思想在统计问题中的应用》 张 宁 -...
50.第一个只出现一次的字符 50.字符流中第一个不重复的字符 51.数组中的逆序对 Array 常考 ...66.构建乘积数组 Array 67.把字符串转成整数 Bit Manipulation 关注 68.树中两个节点的最低公共祖先 常考
累计产品 计算数组的累积乘积。安装$ npm install compute-cprod 要在浏览器中使用,请使用 。用法 var cprod = require ( 'compute-cprod' ) ;cprod( arr[, 选项] ) 计算array的累积乘积。 对于原始arrays , var ...
三个数的最大乘积 思路 最大乘积的可能情况 三个非负数相乘(最大的三个数) 两个非负数和一个负数(这种情况下数组只有这三个数) 一个非负数和两个负数(最小的两个和最大的数) 三个负数(数组都是负数,最大的三...
贪婪问题:•活动选择问题[排序问题[编码[连接问题[支架平衡的交换[货架问题[连接所有城市的成本]]•最大流量问题介绍[数组的乘积子集[K否定后的数组总和[总和] of arr[i]*i[数组的绝对差之和[循环数组中连续差之和...
leetcode 答案 欢迎! 这是我已完成并尝试过的编程问题的集合。...最大的回文乘积 欧拉 2018 年 7 月 30 日 #7 - 第 10 001 个素数 欧拉 2018 年 7 月 29 日 我访问的网站有问题 每周发布 3 个挑战,难
实例047 计算两个矩形矩阵的乘积 75 实例048 获取多维数组的行数与列数 78 实例049 使用快速排序法对一维数组进行排序 79 实例050 使用sort方法对数组进行快速排序 81 实例051 按指定条件在数组中检索元素 82 实例...
有一个数学等式:AB*CD=BA*DC,式中的一个字母代表一位数字,试找出所有符合上述要求的乘积式并打印输出。 2. 编程解决如下问题(50分)。 请在整数n=742683613984中删除8个数字,使得余下的数字按原次序组成...
包含自己发明的一个编程技术(任意维数组)、一个数据结构(多维对称数组)、一个算法(快速方幂和算法);该算法库采用安全的智能指针技术,并且尽量使用了泛型编程。图论算法(兼容有向图,无向图)包括:广度和...
三个数的最大乘积 numEquivDominoPairs 1128. 等价多米诺骨牌对的数量 pivotIndex 724. 寻找数组的中心索引 minimumEffortPath 1631. 最小体力消耗路径(并查集) fairCandySwap 888. 公平的糖果棒交换 fairCandySwap ...
0152.乘积最大子序列 0169.多数元素 0189.旋转数组 0217 0283 0384 0350 0334 0240.搜索二维矩阵 II 0238 链表 0025.K 个一组翻转链表 0138 0141 0148 0160 0206 0234 0237 0328 堆 0155 0215 0295 0378 0347 栈 ...