网易笔试Android编程题第三题最大乘积

有大神共享答案了，穷举法做的： http://blog.csdn.net/siphiababy/article/details/52116246  大神没有加注释，我自己加了注释，希望有用： import java.util.ArrayList; import java.util.List; /**  * 用穷举法，列出了所有可能性  * 原理如下：  * 比如从左到右总共有20个值（编号1,2,3,...,20），而其中按顺序被选中的只有5个，不考虑别的条件，也就是说，此时要把选中的5个的所有可能心都列出来  * 初始为前五个（1,2,3,4,5）,也就是说，最后最大的5个选择只有（16，17，18，19，20）  * 所以之后会有:  * 1,2,3,4,6 1,2,3,4,7 1,2,3,4,8 ... 1,2,3,4,20（只有最后一个数字变化）  * 1,2,3,5,6 1,2,3,5,7 1,2,3,5,8 ... 1,2,3,5,20  * 1,2,3,6,7 1,2,3,6,8 1,2,3,6,9 ... 1,2,3,6,20  * ...  * 1,2,4,5,6 1,2,4,5,7 1,2,4,5,8 ... 1,2,4,5,20  * ...  * 根据规律即可写出相应的代码来列举出所有可能  * 可以看出，每行的每个值都只有最后一个数字在变化，所以每行可以看成是一个集合ai；总共的列数又是一个集合A  *   * 之后根据每行结果中，相邻之间的差d，将不满足要求的ai给remove掉，剩余的集合A就是满足条件的所有情况  * 然后根据A中每个集合元素中的编号，求出最终的最大乘积  */ public class Test_4 { /** *  * @param n 总数 * @param k 按顺序选中的人数 * @param d 编号相邻之间的最大差 * @param a n个人，每人的能力值 * @return */     static int com(int n, int k, int d, int[] a) {         if (n < k || n <= 0 || k <= 0) {             System.out.println("n,k数据输入不合理");             return 0;         }                  //为方便计算，数组坐标从1开始，0不考虑         int[] b = new int[k + 1]; //用来临时存储按先后顺序的k个编号，此时先不考虑编号间的差d         int[] fg = new int[k + 1];  //整个数组a中，最大的一种编号顺序，当然是a的最后k个连续的编号                  for (int i = 1; i <= k; i++) {             b[i] = i;   //初始化时候，第一种最小的情况，就是前k个编号             fg[i] = i - k + n;  //最大的情况，最后k个编号         }                  //（具体看原理解释）泛型为集合，是因为根据前面原理描述的，每行存储多种情况，只有最后一个数字变化。列和列之间，也只有一个数字在变化         List<List<Integer>> comList = new ArrayList<>();           while (true) {             List<Integer> comp = new ArrayList<Integer>();             for (int i = 1; i <= k; i++)                 comp.add(b[i]);  //把规律计算出的可能性存入当前一行的集合 ，行（具体看原理解释）             comList.add(comp);  //放入整个外层集合，列（具体看原理解释）             if (b[1] == n - k + 1)  //当列完了最后一种最大的情况（就是数组的随后k个编号），则退出循环                 break;                          /**              * 此循环的简单解释              * 每种可能中，都从最后一个编号开始计算每种可能性，              * 最后一种全都列举完，那就从倒数第二种开始再列每种可能性，此时要考虑的是最后2个编号的变化，依次3个编号的变化。。。              * 最好看最前面原理中示例的演示              */             for (int i = k; i >= 1; i--) {  //每次用当前的编号顺序和最大的比                 if (b[i] < fg[i]) {                     b[i]++;  //编号顺序的最后一个依次往后递增                     for (int j = i + 1; j <= k; j++)  //此过程需要根据原理中列举的示例来演示，不好描述                         b[j] = b[j - 1] + 1; //后一个起始永远都是前一个加一                     break;                 }             }         }                   //从此时开始考虑编号间隔不大于d         for (int i = 0; i <  comList.size(); i++) {   //剔除所有情况中，不满足间隔不大于d的所有情况             List<Integer> cc = comList.get(i);             for (int j = 1; j < cc.size(); j++) {                 if (cc.get(j) - cc.get(j - 1) > d) {   //发现有超过d的就移除,移除后，当前cc为空，需要跳出当前内部循环                     comList.remove(i);  //移除后，外层集合少去一个，顺序发生变化，所以要i=i-1                     i = i - 1;                     break;                 }             }         }         /**          * 下方不需要再具体解释了，一目了然          */         int max = 0;         for (int i = 0; i < comList.size(); i++) {             int j = 0;             int product = 1;             while (j < k) {             //comList中存储的是每种满足条件的编号序列，可以对应到数组a中取出相应的值             //最初计算编号是按1开始的，所以下方需要-1                 product = product * a[comList.get(i).get(j) - 1];                  j++;             }             if (product > max)                  max = product;         }         return max;     }          public static void main(String[] args) {         int[] i = {5,10,56,-30,-15,-25,-40,26,15,10}; //测试数据         System.out.println(com(10, 3, 3, i));     } }

咦。 那这样子就是穷举法对吧？

记录当前的最大最小，但是最后才发现这个题的数据非常大，还需要用大数么？。。

每次DP 记录最大最小。 注意合理初始化就行了

Leetcode原题 我记得

最大最小一起搞？