内容简介:给定一个数组, 找出数组子集乘积的最大值比如[2, 3, -2, 4] 数组, 子集有 [2,3], [2,3,-2], [2,3,-2,4], [3,-2], [3,-2,4], [-2,4]每个乘积为 6, -12, -48, -6, -24, -8 所以最大值为 6
给定一个数组, 找出数组子集乘积的最大值
比如[2, 3, -2, 4] 数组, 子集有 [2,3], [2,3,-2], [2,3,-2,4], [3,-2], [3,-2,4], [-2,4]
每个乘积为 6, -12, -48, -6, -24, -8 所以最大值为 6
分析
首先要找出子集, 对于一个数组来说, 在程序里找子集可以通过for循环来找, 然后把子集的各项相乘即可, 好在只用算乘积, 乘法满足交换率, 可以不分先后顺序这样就简单的多了
然后再从各项乘积里找出最大项, 可以使用Math类的max方法来找, 下面来看一下代码
解法
找出数组子集并做乘法运算
// 计算数组中的所有字集的积 private List<Integer> multiply(List<Integer> result, int current, int... num) { if (num.length == 0) return result; if (num.length == 1) { result.add(num[0]); return result; } if (current == num.length - 1) return result; int temp = 0; for (int i = current; i < num.length - 1; i++) { if (i == current) { temp = num[i] * num[i + 1]; } else { temp *= num[i + 1]; } result.add(temp); } return multiply(result, current + 1, num); }
原链接文: https://tomoya92.github.io/2019/04/27/algorithm-1/
因为Math.max()方法只有两个参数, 可以进行封装, 让它支持对集合中数字的大小比较
// 找一个集合里最大的数 private Integer max(Integer init, int current, List<Integer> num) { if (num.size() == 0) return null; if (num.size() < 2) return num.get(0); if (init == null) { return max(Math.max(num.get(0), num.get(1)), current + 2, num); } else { if (current == num.size() - 1) return init; return max(Math.max(init, num.get(current)), current + 1, num); } }
然后只管调用方法即可
@Test public void test() { int[] a = new int[]{2, 3, -2, 4}; List<Integer> result = multiply(new ArrayList<>(), 0, a); System.out.println("所有字集的积: " + result); System.out.println(max(null, 0, result)); }
优解
网上有大神给出了简便的写法, 一个for循环即可解决, 代码如下
@Test public void test1() { int[] nums = new int[]{2, 3, -2, 4}; int max = nums[0], min = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { int temp = max; max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]); if (max > result) { result = max; } } System.out.println(result); }
写博客不易,转载请保留原文链接,谢谢!
原文链接:
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 力扣152——乘积最大子序列
- 蓝桥杯 ADV-189 算法提高 连接乘积
- Leetcode日记_01,乘积最大子序列
- 蓝桥杯 ADV-13 算法提高 最小乘积(提高型)
- LeetCode每日一题: 三个数的最大乘积(No.628)
- 【 数据集合】并集、交集、差集、子集
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
打造Facebook
王淮、祝文让 / 印刷工业出版社 / 2013-2-1 / 39.80元
《打造Facebook》新书发布会,王淮与读者面对面,活动链接:http://www.douban.com/event/18166913/ 这本书的书名——《打造Facebook:亲历Facebook爆发的5年》很嚣张,谁有资格可以说这句话呢,当然,扎克伯格最有资格,但他不会亲自来告诉你,至少从目前的情况来看,近几年都不大可能。而且,这不是一个人的公司。里面的每一人,尤其是工程师,既是公司文......一起来看看 《打造Facebook》 这本书的介绍吧!