[Google Interview] No. 28 - A Pair with the Maximal Difference

Problem: A pair contains two numbers, and its second number is on the right side of the first one in an array. The difference of a pair is the minus result while subtracting the second number from the first one. Please implement a function which gets the maximal difference of all pairs in an array. For example, the maximal difference in the array {2, 4, 1, 16, 7, 5, 11, 9} is 11, which is the minus result of pair (16, 5).



Solution with O(nxn) and O(n):

#include <iostream>

using namespace std;

void print (int *list, int num)
{
        for (int i=0; i<num; i++)
        {
                cout << list[i] << " ";
        }
        cout << endl;
}

// O(nxn)
int getMaxPairSol1(int *list, int num)
{
        int i, j, curMax=0, diff=0;
        if ( !list || (num < 2) )
        {
                return 0;
        }

        for (i=0; i<(num-1); i++)
        {
                for (j=(i+1); j<num; j++)
                {
                        diff = list[i]-list[j];
                        if (diff > curMax)
                        {
                                curMax = diff;
                                cout << list[i] << "(" << i << ") - " << list[j] << "(" << j << ") = " << curMax << endl;
                        }
                }
        }

        return curMax;
}

// O(n)
int getMaxPairSol2(int *list, int num)
{
        int i, j, curMax=0, diff=0,diffMax=0;
        int start=0, end=0;

        if ( !list || (num < 2) )
        {
                return 0;
        }

        curMax = list[1];
        diff = list[0] - curMax;
        diffMax = diff;

        for (i=2; i<num; i++)
        {
                if (list[i-1] > curMax)
                {
                        start = i-1;
                        curMax = list[i-1];
                }

                diff = curMax - list[i];
                if (diff > diffMax)
                {
                        end = i;
                        diffMax = diff;
                }
        }

        cout << list[start] << "(" << start << ") - " << list[end] << "(" << end << ") = " << diffMax << endl;
        return diffMax;
}

int main(int argc, char **argv)
{
        int list[]={2, 4, 1, 16, 15, 7, 5, 11, 9};
        int maxRes=0;

        print (list, sizeof(list)/sizeof(list[0]));
        //maxRes = getMaxPairSol1(list, sizeof(list)/sizeof(list[0]));
        maxRes = getMaxPairSol2(list, sizeof(list)/sizeof(list[0]));
        cout << "maxRes=" << maxRes << endl;

        return 0;

}

ref: http://codercareer.blogspot.tw/2011/12/no-28-pair-with-maximal-difference.html