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

February 26, 2012 Posted by | C++ | , , , , | Leave a comment