Ronzii's Blog

Just your average geek's blog

Given an array A[], find (i, j) such that A[i] < A[j] and (j – i) is maximum.

#include<iostream>
#include<vector>
using namespace std;
void printArray(vector<int> a)
{
    for(vector<int>::iterator itr=a.begin(); itr!=a.end(); itr++)
    {
        cout<<*itr<<" ";
    }
    cout<<endl;
}
void MaxDifference(vector<int> a)
{
    int n = a.size();
    vector<int> Lmin(n,0);
    vector<int> Rmax(n,0);
    Lmin[0] = a[0];
    for(int i=1; i<n; i++)
        Lmin[i] = min(a[i],Lmin[i-1]);
    Rmax[n-1] = a[n-1];
    for(int j=n-2; j>=0; j--)
        Rmax[j] = max(a[j],Rmax[j+1]);
    printArray(Lmin);
    printArray(Rmax);
    int i=0,j=0,maxdiff=0;
    while(i<n && j<n)
    {
        if(Lmin[i]<Rmax[j])
        {
            maxdiff = max(maxdiff,j-i);
            j++;
        }
        else
        {
            i++;
        }
    }
    cout<<maxdiff;
}
int main()
{
    int a[] = {3,1,4,5,2,1,2};
    vector<int> v(a,a+sizeof(a)/sizeof(int));
    printArray(v);
    MaxDifference(v);
    return 0;
}
Advertisements

February 26, 2012 Posted by | C++ | , , , , | Leave a 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