Ronzii's Blog

Just your average geek's blog

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;
}

March 31, 2012 Posted by | C++ | , , , , , | 1 Comment

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;
}

July 7, 2011 Posted by | C++ | , , | 3 Comments