演算法 - 找出陣列中子集乘積的最大值
給定一個數組, 找出陣列子集乘積的最大值
比如[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); }
寫部落格不易,轉載請保留原文連結,謝謝!
原文連結: