## Maximum Sum in a Tree

#include <iostream> #include <climits> using namespace std; struct node { int value; struct node *left; struct node *right; }; typedef struct node TreeNode; int treeMin = INT_MAX; TreeNode* createNode(int n) { TreeNode *temp = new TreeNode; temp->value = n; temp->left = NULL; temp->right = NULL; return temp; } int max5(int a, int b,int c, int d, int e) { return max(a,max(b,max(c,max(d,e)))); } int maxSumTree(TreeNode* current, int* sum) { if(current==NULL) { *sum = treeMin; return treeMin; } else { int ls = INT_MIN,rs = INT_MIN; int l = maxSumTree(current->left,&ls); int r = maxSumTree(current->right,&rs); *sum = max5(*sum,current->value, ls+rs+current->value,ls+current->value,rs+current->value); return max(*sum,max(l,r)); } } void binaryTreeMin(TreeNode* current) { if(current==NULL) return; binaryTreeMin(current->left); if(treeMin>current->value) treeMin = current->value; binaryTreeMin(current->right); } int main() { TreeNode* root = createNode(17); root->left = createNode(15); root->right = createNode(-20); root->left->left = createNode(13); root->left->left->left = createNode(-15); root->left->left->right = createNode(-7); root->right->left = createNode(50); root->right->right = createNode(-72); binaryTreeMin(root); int sum = treeMin; cout<<maxSumTree(root,&sum); return 0; }

Advertisements

## Fast Input SPOJ

Recently, I have gotten into solving problems in SPOJ. Here is a snippet, I often use to get fast input. This has helped me get AC in several problems that I was previously getting time limit exceeded.

#include <iostream> #include <cstdio> namespace IO { const int SIZE = 1 << 19; char buff[SIZE], *p = buff + SIZE; char read_char() { if( p == buff + SIZE ) { fread( buff, 1, SIZE, stdin ); p = buff; } return *(p++); } inline int read_int() { char c; while( !isdigit( c = read_char() ) ); int r = c-'0'; while( isdigit( c = read_char() ) ) r = 10*r + c - '0'; return r; } } using namespace IO; using namespace std; int main() { int t; t = read_int(); cout<<t; return 0; }

Advertisements