Largest Rectangle in a Histogram

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll arr[100005];
struct data
{
    ll sum,mini;
};
data tree[4*100000];
void build(ll node, ll b, ll e)
{
    if(b==e)
    {
        tree[node].sum=tree[node].mini=arr[b];
        return;
    }
    ll left,right,mid;

    mid=(b+e)/2;

    left=2*node;
    right=2*node+1;

    build(left,b,mid);
    build(right,mid+1,e);

    tree[node].mini=min(tree[left].mini,tree[right].mini);
    tree[node].sum=max( max(tree[left].sum,tree[right].sum),tree[node].mini*(e-b+1) );
}

int main()
{
    ll n,m,i,j;
    while(scanf("%lld",&n) && n)
    {
        memset(tree,0,sizeof tree);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&arr[i]);
        }
        build(1,1,n);
        printf("%lld\n",tree[1].sum);
    }
    return 0;
}