fork download
copy 
  1. var counter = 0;
  2.  
  3. function getTreeDepth(tree) {
  4. 	if (tree.length == 0 || tree.length == 1) {
  5. 		return tree.length;
  6. 	}
  7.  
  8. 	depth = 1;
  9. 	increment = 1;
  10. 	maxIndex = 1;
  11.  
  12. 	while(maxIndex < tree.length) {
  13. 		increment ++;
  14. 		maxIndex += increment;
  15. 		depth ++;
  16. 	}
  17.  
  18. 	return depth;
  19. }
  20.  
  21. function maxSum(tree, treeDepth, rootIndex, rootDepth) {
  22. 	counter++;
  23. 	if (rootDepth == treeDepth) {
  24. 		return tree[rootIndex];
  25. 	}
  26.  
  27. 	// Recursive step:
  28. 	var leftSubTreeSum = maxSum(tree, treeDepth, rootIndex + rootDepth, rootDepth + 1);
  29. 	var rightSubTreeSum = maxSum(tree, treeDepth, rootIndex + rootDepth + 1, rootDepth + 1);
  30. 	var maxSubTreeSum;
  31.  
  32. 	if (rightSubTreeSum > leftSubTreeSum) {
  33. 		maxSubTreeSum = rightSubTreeSum;
  34. 	} else {
  35. 		maxSubTreeSum = leftSubTreeSum;
  36. 	}
  37.  
  38. 	return tree[rootIndex] + maxSubTreeSum;
  39. }
  40.  
  41. //NOTE: children of tree[n] are tree[n + depthOfN] and tree[n + depthOfN + 1]
  42. var tree = [75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 04, 82, 47, 65, 19, 01, 23, 75, 03, 34, 88, 02, 77, 73, 07, 63, 67, 99, 65, 04, 28, 06, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23];
  43. var treeDepth = getTreeDepth(tree);
  44. print("Max sum of traversal = " + maxSum(tree, treeDepth, 0, 1));
  45. print(counter);
Success #stdin #stdout 0.04s 4984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max sum of traversal = 1074
32767
https://ideone.com/TKoNK
language:
JavaScript (SMonkey 60.2.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!