1. /**
    2.  * 最大快乐值
    3.  * 公司的每个员工共都符合Employee类的描述.整个公司的人员结构可以看作是一颗标准的，没有环的多
    4.  * 叉树。树的头节点是公司唯一的老板，除老板之外的每一个员工都有一个唯一的直接上级。叶节点是没
    5.  * 有任何下属的基层员工（subordinates列表为空），除基层员工之外，每个员工都有一个或者多个直
    6.  * 接下级。
    7.  */
    8. public class Code04_MaxHappy {
    10.     public static class Employee {
    11.         public int happy;              // 快乐值
    12.         public List<Employee> nexts; // 直系下级
    14.         public Employee(int h) {
    15.             happy = h;
    16.             nexts = new ArrayList<>();
    17.         }
    19.     }
    21.     public static int maxHappy1(Employee boss) {
    22.         if (boss == null) {
    23.             return 0;
    24.         }
    25.         return process1(boss, false);
    26.     }
    28.     // 当前来到的节点叫cur，
    29.     // up表示cur的上级是否来，
    30.     // 该函数含义：
    31.     // 如果up为true，表示在cur上级已经确定来，的情况下，cur整棵树能够提供最大的快乐值是多少？
    32.     // 如果up为false，表示在cur上级已经确定不来，的情况下，cur整棵树能够提供最大的快乐值是多少？
    33.     public static int process1(Employee cur, boolean up) {
    34.         if (up) { // 如果cur的上级来的话，cur没得选，只能不来
    35.             int ans = 0;
    36.             for (Employee next : cur.nexts) {
    37.                 ans += process1(next, false);
    38.             }
    39.             return ans;
    40.         } else { // 如果cur的上级不来的话，cur可以选，可以来也可以不来
    41.             int p1 = cur.happy;
    42.             int p2 = 0;
    43.             for (Employee next : cur.nexts) {
    44.                 p1 += process1(next, true);
    45.                 p2 += process1(next, false);
    46.             }
    47.             return Math.max(p1, p2);
    48.         }
    49.     }
    51.     /**
    52.      * 递归套路解决
    53.      */
    54.     public static int maxHappy2(Employee head) {
    55.         Info allInfo = process(head);
    56.         return Math.max(allInfo.no, allInfo.yes);
    57.     }
    59.     public static class Info {
    60.         public int no;  // 头节点不来时的最大happy收益
    61.         public int yes; // 头节点来时的最大happy收益
    63.         public Info(int n, int y) {
    64.             no = n;
    65.             yes = y;
    66.         }
    67.     }
    69.     public static Info process(Employee x) {
    70.         if (x == null) {
    71.             return new Info(0, 0);
    72.         }
    73.         int no = 0;
    74.         int yes = x.happy;
    75.         // 获取后代信息
    76.         for (Employee next : x.nexts) {
    77.             Info nextInfo = process(next);
    78.             no += Math.max(nextInfo.no, nextInfo.yes);// 头节点来时，最大happy收益值
    79.             yes += nextInfo.no;
    81.         }
    82.         return new Info(no, yes);
    83.     }
    85.     // for test
    86.     public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
    87.         if (Math.random() < 0.02) {
    88.             return null;
    89.         }
    90.         Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
    91.         genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
    92.         return boss;
    93.     }
    95.     // for test
    96.     public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
    97.         if (level > maxLevel) {
    98.             return;
    99.         }
    100.         int nextsSize = (int) (Math.random() * (maxNexts + 1));
    101.         for (int i = 0; i < nextsSize; i++) {
    102.             Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
    103.             e.nexts.add(next);
    104.             genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
    105.         }
    106.     }
    108.     public static void main(String[] args) {
    109.         int maxLevel = 4;
    110.         int maxNexts = 7;
    111.         int maxHappy = 100;
    112.         int testTimes = 100000;
    113.         for (int i = 0; i < testTimes; i++) {
    114.             Employee boss = genarateBoss(maxLevel, maxNexts, maxHappy);
    115.             if (maxHappy1(boss) != maxHappy2(boss)) {
    116.                 System.out.println("Oops!");
    117.             }
    118.         }
    119.         System.out.println("finish!");
    120.     }
    122. }