title: Given Parent Array and Values Array. Find Best Possible Sum in a tree
body: <p>Given Parent Array Such that parent[i]=j where j is the parent and Value array . Need to Find Best possible sum.</p>
  
  <p>Root node will have -1 as parent.</p>
  
  <p>Best Possible sum is maximum sum in one of the tree paths.</p>
  
  <p>Ex)</p>
  
  <pre><code> Integer[] parent = new Integer[] { -1, 0, 0, 2, 3 };
   Integer[] values = new Integer[] { 0, 4, 6, -11, 3 };
  
       (0/0)----(1/4)
       |
       |
       (2/6)
       |
       |
       (3/-11)
       |
       |
       (4/3)
  </code></pre>
  
  <p>Maximum sum here would be  6+0+4=10 for path 2-->0-->1.</p>
  
  <p>I have tried solving it the dfs way. But not sure if it works for all cases. Below is my code. It gives all possible sum. we can take out max from that.</p>
  
  <pre><code>    package com.programs.algo;
  
      import java.util.ArrayList;
      import java.util.Arrays;
      import java.util.List;
      import java.util.stream.Collectors;
  
      public class BestPossibleSum {
  
          static class Node&lt;T&gt; {
  
          T label;
          T data;
          List&lt;Node&lt;T&gt;&gt; nodes;
         }
  
  public static void main(String[] args) {
  
      Integer[] parent = new Integer[] { -1, 0, 0, 1, 1, 3, 5 };
      Integer[] values = new Integer[] { 0, 4, 6, -11, 3, 10, 11 };
  
      List&lt;Integer&gt; list1 = new ArrayList&lt;&gt;(Arrays.asList(parent));
      List&lt;Integer&gt; list2 = new ArrayList&lt;&gt;(Arrays.asList(values));
      bestPossibleSum(list1, list2);
  }
  
  static List&lt;Node&lt;Integer&gt;&gt; tree = new ArrayList&lt;&gt;();
  
  private static void bestPossibleSum(List&lt;Integer&gt; list1, List&lt;Integer&gt; list2) {
      int adj[][] = new int[list1.size()][list1.size()];
      createTree(list1, list2, adj);
      List&lt;Integer&gt; traversedNodes = new ArrayList&lt;&gt;();
      List&lt;Integer&gt; sumOfraversedNodes = new ArrayList&lt;&gt;();
  
      for (int i = 0; i &lt; adj.length; i++) {
          dfs(tree.get(i), traversedNodes, sumOfraversedNodes);
          traversedNodes.clear();
      }
  
      System.out.println(sumOfraversedNodes);
  }
  
  private static void dfs(Node&lt;Integer&gt; tree, List&lt;Integer&gt; traversedNodes, List&lt;Integer&gt; sums) {
      if (!traversedNodes.contains(tree.label)) {
          traversedNodes.add(tree.label);
          sums.add(getSum(traversedNodes));
          for (Node&lt;Integer&gt; child : tree.nodes) {
              dfs(child, traversedNodes, sums);
          }
      }
  }
  
  private static Integer getSum(List&lt;Integer&gt; traversedNodes) {
      System.out.println(traversedNodes);
      return traversedNodes.stream().reduce(0, Integer::sum);
  }
  
  private static void createTree(List&lt;Integer&gt; parent, List&lt;Integer&gt; values, int[][] adj) {
  
      for (int i = 0; i &lt; parent.size(); i++) {
          Node&lt;Integer&gt; node = new Node&lt;&gt;();
          node.label = i;
          node.data = values.get(i);
          node.nodes = new ArrayList&lt;&gt;();
          tree.add(i, node);
      }
  
      for (int i = 0; i &lt; parent.size(); i++) {
          if (parent.get(i) != -1) {
              adj[parent.get(i)][i] = 1;
              adj[i][parent.get(i)] = 1;
              tree.get(parent.get(i)).nodes.add(tree.get(i));
          }
      }
  
      tree.forEach(t -&gt; {
          System.out.println(t.label);
          System.out.println(t.nodes.stream().map(m -&gt; m.label).collect(Collectors.toList()));
      });
      // System.out.println(Arrays.deepToString(adj));
  }
  </code></pre>
  
  <p>}</p>