[Snapchat]Company Party Dynamic programming

1. Example

              A
      /        |        \
     B       C -F      D-E
      |
     G

Case 1:
              A go
      /         |        \
     BNgoC -F      D-E
      |         Ngo     Ngo
     G go

Case2:
              A  nogo
      /        |        \
     B go  C -F   D-E
      |         go     go
     G nogo

Every node can go or nogo
go     => vlaue = node.rating;
nogo => value = 0;
     
2. Implementation

// time :O(2^n)

// ArrayList listOfStrings = new ArrayList<>(list.size());
// listOfStrings.addAll(list);
public List guestList(Node[] nodes)
{
      
      List maxlist = new ArrayList();
      int maxSum = 0;
      for (int i =0 ; i < nodes.length; i++)
      {
             List list = new ArrayList();
             int sum = FindMaxRating(nodes[i], list);
             if (  sum > maxSum )
             {
                  maxSum = sum;
                  maxList = new ArrayList(list);
                  list = null;
             }  
      }

}

private int FindMaxRating(Node node, List list)
{
      if ( node.children == null)
          return Math.max(0, node.rating);
      else      
      {
           
          int childrenSum = 0;
          for ( Node c: node.children)
          {
              childrenSum += FindMaxRating(c, list);
          }
          int grandChildrenSum  = node.rating;
          
          for (Node c: node.grandchildren)
          {
              grandChildrenSum += FindMaxRating(c, list);

          }
          return Math.max( childrenSum, grandChildrenSum  );
      }
}       

// Time:O(n)

public  List guestList(Node[] nodes)
{
     

      int[] MC = new int[nodes.length];
      for (i = nodes.length-1 ; i>=0; i++)
      {
          if (nodes[i].children == null || nodes[i].grandChildren == null)
               MC[i]  = Math.max(0+ node.rating, 0);
          else
               MC[i] = Math.max(   node.rating+ sumOfAll(node.children), 0 + sumOfAll(node.grandChildren) );
      }

     
      return MC[0];
}

private int sumOfAll(Node[] children)
{
      int sum = 0; 
      for (Node c: children)
      {
         sum+= c.rating;
      }
      return sum;
}

// Time:O(2n), n is the number of nodes

typredef struct Node
{
   int rating;
   int *parent, *leftChild, *rightSibling;
   int sel, unsel;
   int go; 
} Node;
typedef struct stack
{
   int *top, *base;
   int stackSize;
} Stack;
void traverse (Node *T)
{
      Stack s;
      s.top =1;
      Node *r;
      r = T;
      while(top != -1 || r != null )
      {
          s.top++;
          *s.top = r;
          while(   r.leftChild != null ) // add
          {
              s.top++;
              *s.top = r.leftchild;
              r = r.leftChild;
          }

          r = *s.top; // pop
          s.top--;

   
          // 
          if (r.leftChild == null) // check if leave
          {
              r.sel = r.rating;
              r.unsel = 0;
          }
          else // not a leaf
          {
              r.sel = r.rating + sum( j.unsel );
              r.unsel = sum ( max{ j.unselect, j.sel} );
          }
          
          r = r.rightSibling;
      }
}
void find_the_list(Node *T)
{

   Node *r, *s;
   r = T;
   if (  r == null ) return ;
   else if ( r.parent == NULL ) 
   {
        if ( r.select > r.unselct )
              r.go = 1;
         else
              r.go =0;
   }
   else 
   {
        if (r.parent.go ==1)
              r.go = 0;
         else
         {
            if ( r.unselect < r.select)
              r.go = 0;
            else
              r.go = 1;
         }
   }
   
   r = r.leftChild;
   s= r.rightSibling;
   find_the_list(r);
   find_the_list(s);
    
   // Print out those go ==1       
}

3. Similar Ones
http://mypathtothe4.blogspot.com/2013/03/dynamic-programming-company-party.html
http://blog.csdn.net/edonlii/article/details/8623058