findMaxScore

gistfile1.cpp

struct Node
{
	int score;
	Node* left;
	Node* right;
};

//M(r,k) returns the maximum sum of score of size k from root r.  M(r,k) = max( M(l,i), M(r,j)); i+j = k and i,j>0
int findMaxScore(Node* node, int k) {
	vector<int> sum;
	vector<int>::const_iterator it;

	if (node == NULL) return -1; // wrong pruning
	if (k == 1) return node->score;

	for (int i = 1; i < k; ++i){
		int left = findMaxScore(node->left, i);
		int right = findMaxScore(node->right, k - i);

		if (left != -1 && right != -1) sum.push_back(left+right);
	}
	
	if (sum.size() > 0) return *(max_element(sum.begin(), sum.end())); //O(n);
	else return -1;
}