0915 广发银行笔试

//先全排列得出所有可能放入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;
            }
        }
    }

//暴力法，没啥说的
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;
    }