算法 - 找出数组中子集乘积的最大值

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个数组, 找出数组子集乘积的最大值比如[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);
}

写博客不易,转载请保留原文链接,谢谢!

原文链接:


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

PHP典型模块与项目实战大全

PHP典型模块与项目实战大全

杨宇 / 清华大学出版社 / 2012-1 / 79.00元

《PHP典型模块与项目实战大全》以实战开发为原则,以PHP典型模块和项目开发为主线,通过12个高质量的PHP典型模块和6个PHP大型应用,向读者揭示了Web开发的整体结构,并详尽地介绍PHP开发与建站的技术要点。《PHP典型模块与项目实战大全》附带1张DVD,内容是作者为《PHP典型模块与项目实战大全》录制的全程多媒体语音教学视频及《PHP典型模块与项目实战大全》所涉及的源代码。《PHP典型模块与......一起来看看 《PHP典型模块与项目实战大全》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具