Given an array arr[], find the maximum j – i such that arr[j] > arr[i]

package test;

class FindMaximum

{

    /* Utility Functions to get max and minimum of two integers */

    int max(int x, int y) 

    {

        return x > y ? x : y;

    }

    int min(int x, int y) 

    {

        return x < y ? x : y;

    }

    /* For a given array arr[], returns the maximum j-i such that

       arr[j] > arr[i] */

    int maxIndexDiff(int arr[], int n) 

    {

        int maxDiff;

        int i, j;

        int RMax[] = new int[n];

        int LMin[] = new int[n];

        /* Construct LMin[] such that LMin[i] stores the minimum value

           from (arr[0], arr[1], ... arr[i]) */

        LMin[0] = arr[0];

        for (i = 1; i < n; ++i)

            LMin[i] = min(arr[i], LMin[i - 1]);

        /* Construct RMax[] such that RMax[j] stores the maximum value

           from (arr[j], arr[j+1], ..arr[n-1]) */

        RMax[n - 1] = arr[n - 1];

        for (j = n - 2; j >= 0; --j)

            RMax[j] = max(arr[j], RMax[j + 1]);

        /* Traverse both arrays from left to right to find optimum j - i

           This process is similar to merge() of MergeSort */

        i = 0; j = 0; maxDiff = -1;

        while (j < n && i < n) 

        {

            if (LMin[i] < RMax[j]) 

            {

                maxDiff = max(maxDiff, j - i);

                j = j + 1;

            } 

            else

                i = i + 1;

        }

        return maxDiff;

    }

    

    int maxIndexDiff1(int a[] , int n)

    {

     

    int i=0,j=n-1;

    while(i<=j)

    {

     

     

    if(a[j]>a[i])

    {

     

    return j-i;

    }

     

    if(a[j-1]>a[i])

     j--;

    else if(a[i+1]<a[j])

     i++;

    else

    {

    i++;

    j--;

    }

     

    }

     

    return -1;

     

     

    }

    /* Driver program to test the above functions */

    public static void main(String[] args) 

    {

        FindMaximum max = new FindMaximum();

        int arr[] = {6, 5, 4, 3, 2, 1};

        int n = arr.length;

        int maxDiff = max.maxIndexDiff(arr, n);

        int maxDiff1 = max.maxIndexDiff1(arr, n);
maxIndexDiff1 wont work for below two arrays.

{10,11,12,13,14,6,9,7,5,3} : expected: 4, given -1 

{6,9,7,5,3} :  expected 2, given -1

        System.out.println(n + " " + maxDiff + " " +maxDiff1);

    }

}

Code for remote debug

-Xdebug -Xrunjdwp:server=y,transport=dt_socket,address=7000,suspend=n

insert script for NT_Property table for R2R

Insert into nt_property (NAME,VALUE,NOTE) values ('nextLongId','8005149766','next starting id for this database owner');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextId','108218669','next starting id for this database owner');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxLongId','9999999999','the max id');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxId','0','the max id');

Insert into nt_property (NAME,VALUE,NOTE) values ('idManager',null,'IdManager for this RMOB schema.');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextNodePvid','521732848','next starting id for NODE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxNodePvid','2000000000','max id for NODE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextLinkPvid','521736970','next starting id for LINK PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxLinkPvid','2000000000','max id for LINK PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextFacePvid','521727318','next starting id for FACE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxFacePvid','2000000000','max id for FACE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextRoadLinkPvid','521755019','next starting id for ROAD_LINK PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxRoadLinkPvid','2000000000','max id for ROAD_LINK PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextCartoPvid','521727314','next starting id for CARTO PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxCartoPvid','2000000000','max id for CARTO PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextNamedPlacePvid','521727290','next starting id for NAMED_PLACE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxNamedPlacePvid','2000000000','max id for NAMED_PLACE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextMultiNavPvid','521727286','next starting id for MULTI_NAV PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxMultiNavPvid','2000000000','max id for MULTI_NAV PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextPoiPvid','521727331','next starting id for POI PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxPoiPvid','2000000000','max id for POI PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextAssocPvid','521727286','next starting id for ASSOC PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxAssocPvid','2000000000','max id for ASSOC PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextNamePvid','521727561','next starting id for NAME PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxNamePvid','2000000000','max id for NAME PVIDS ');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextValuePvid','521727286','next starting id for VALUE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxValuePvid','2000000000','max id for VALUE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextRoadPointPvid','521727286','next starting id for ROADPOINT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxRoadPointPvid','2000000000','max id for ROADPOINT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitCompanyPvid','521727286','next starting id for TRANSIT COMPANY PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitCompanyPvid','2000000000','max id for TRANSIT COMPANY PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitSystemPvid','521727286','next starting id for TRANSIT SYSTEM PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitSystemPvid','2000000000','max id for TRANSIT SYSTEM PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitLinePvid','521727286','next starting id for TRANSIT LINE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitLinePvid','2000000000','max id for TRANSIT LINE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitStopPvid','521727286','next starting id for TRANSIT STOP PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitStopPvid','2000000000','max id for TRANSIT STOP PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitPlatformPvid','521727286','next starting id for TRANSIT PLATFORM PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitPlatformPvid','2000000000','max id for TRANSIT PLATFORM PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitStrandPvid','521727286','next starting id for TRANSIT STRAND PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitStrandPvid','2000000000','max id for TRANSIT STRAND PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitAccessPvid','521727286','next starting id for TRANSIT ACCESS PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitAccessPvid','2000000000','max id for TRANSIT ACCESS PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitTransferPvid','521727286','next starting id for TRANSIT TRANSFER PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitTransferPvid','2000000000','max id for TRANSIT TRANSFER PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitGuidancePvid','521727286','next starting id for TRANSIT GUIDANCE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitGuidancePvid','2000000000','max id for TRANSIT GUIDANCE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitSegmentPvid','521727286','next starting id for TRANSIT SEGMENT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitSegmentPvid','2000000000','max id for TRANSIT SEGMENT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTransitStopAreaPvid','521727286','next starting id for TRANSIT STOP AREA PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTransitStopAreaPvid','2000000000','max id for TRANSIT STOP AREA PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextFeaturePointPvid','521727286','next starting id for FEATURE POINT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxFeaturePointPvid','2000000000','max id for FEATURE POINT PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextMapObjectAssocPvid','521727286','next starting id for MAP OBJECT ASSOCIATION PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxMapObjectAssocPvid','2000000000','max id for MAP OBJECT ASSOCIATION PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextNavLanePvid','521727286','next starting id for NAVLANE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxNavLanePvid','2000000000','max id for NAVLANE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextLaneStrandPvid','521727286','next starting id for NAVLANE PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxLaneStrandPvid','2000000000','max id for LANESTRAND PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextTopologySegmentPvid','521727286','next starting id for Topology Segment PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxTopologySegmentPvid','2000000000','max id for Topology Segment PVIDS');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextVariableSpeedSignId','51001','next starting id for VARIABLE SPEED SIGN ID');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxVariableSpeedSignId','9999999999','max id for VARIABLE SPEED SIGN ID');

Insert into nt_property (NAME,VALUE,NOTE) values ('nextMetadataId','8999000000','next starting id for metadata');

Insert into nt_property (NAME,VALUE,NOTE) values ('maxMetadataId','2000000000','max id for metadata');

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalNamedPlacePvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalNodePvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalLinkPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalAssocPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalPoiPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalRoadLinkPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalRoadPointPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalValuePvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalCartoPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalFacePvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalMultiNavPvid','5861800',null);

Insert into nt_property (NAME,VALUE,NOTE) values ('lastGlobalNamePvid','5861800',null);

commit;