-
//先全排列得出所有可能放入res,然后计算res中所有的集合的乘积大小,全排列本身是有序的 boolean[] used; List<List<Integer>> res; Deque<Integer> path; public int[] findCombination (int n, int[] srcArr) { // write code here res = new ArrayList<>(); path = new ArrayDeque<>(); used = new boolean[srcArr.length]; int len = srcArr.length; quanpailie(n,srcArr); int max = 0; int[] a = new int[n]; for (List<Integer> re : res) { int num = dfs(0,re.size()-1,re); if(num > max){ max = num; int index = 0; for (Integer integer : re) { a[index++] = integer; } } } return a; } public int dfs(int start , int end,List<Integer> list){ if(end<=start){ return 0; } int sum = 0; for(int i = start+1; i <=end ; i++){ sum +=list.get(start)*list.get(i); } return sum + dfs(start+1,end,list); } public void quanpailie(int n,int []srcArr){ if(path.size() == n){ res.add(new ArrayList<>(path)); } for (int i = 0; i < srcArr.length; i++) { if(!used[i]){ used[i] = true; path.addLast(srcArr[i]); quanpailie(n ,srcArr); path.removeLast(); used[i] = false; } } }
2.//暴力法,没啥说的 public int calcMaxRusult (int[] srcArr) { // write code here int n = srcArr.length; int res =0; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { for (int k = j+1; k < n; k++) { int num = srcArr[i]*srcArr[j]+srcArr[i]*srcArr[k]+srcArr[j]*srcArr[k]; res = Math.max(res,num); } } } return res; }
全部评论
(5) 回帖