//find the maximum sum of subtree
public class GlobalOptimumOne {
static public int max = Integer.MIN_VALUE;
public static void main(String... args) {
int[] values = {10, -5, -20, 3, -15, 7, 26, -9, 14};
System.out.println("inserting order");
for(int i = 0; i < values.length; i++) {
System.out.print(values[i] + " ");
}
System.out.println();
System.out.println("Layer order");
BTree root = buildTree(values);
BTreePrinter.printNode(root);
maxSum(root);
System.out.println("max subtree");
System.out.println(max);
}
public static int maxSum(BTree root) {
if(root == null) return 0;
int leftSum = 0, rightSum = 0;
if(root.left != null) {
leftSum = maxSum(root.left);
}
if(root.right != null) {
rightSum = maxSum(root.right);
}
int sum = leftSum + rightSum + root.value;
//System.out.println("sum=" + sum);
max = Math.max(max, sum);
return sum;
}
//build a binary search tree
public static BTree buildTree(int[] values) {
BTree root = null;
for(int value : values) {
root = insert(root, value);
}
return root;
}
public static BTree insert(BTree root, int value) {
if(root == null) {
return new BTree(value, null, null);
}
if(value > root.value) {
root.right = insert(root.right, value);
return root;
}
if(value < root.value) {
root.left = insert(root.left, value);
return root;
}
root.value = value;
return root;
}
}
