数对之差的最大值[算法]

 

题目:在数组中,数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中,数对之差的最大值是11,是16减去5的结果。

#include<stdio.h>
#include<stdlib.h>

int maxDiff( int *array, unsigned length );
int getDiff( int *start, int *end, int **max, int **min );
int maxDiff2( int *num, unsigned length );
int getDiff2( int *num, unsigned length );
int maxDiff3( int *num, unsigned length );

int main( void )
{
    int num[] = { 2, 4, 1, 16, 7, 5, 11, 9, 20, 1 };
    //int num[] = { 2, 4, 1};
    int *arr = num;

    int result = maxDiff( arr, sizeof( num ) / sizeof(int) );

    printf( "by recursive : \n" );
    printf( "%d\n", result );

    result = maxDiff2( arr, sizeof( num ) / sizeof(int) );
    printf( "by dp1 : \n" );
    printf( "%d\n", result );

    result = maxDiff3( arr, sizeof( num ) / sizeof(int) );
    printf( "by dp2 : \n" );
    printf( "%d\n", result );
    return 0;
}

int maxDiff( int *num, unsigned length )
{
    int *max ;
    int *min;

    if( length < 2 )
    {
        return -1;
    }
    else if( length == 2 )
    {
        return *num >= *( num + 1 ) ? ( *num - *( num + 1 ) ) : ( *( num + 1 ) - *num );
    }
    return getDiff( num, num + length-1, &max, &min );

}

// using recursive to get the result
int getDiff( int *start, int *end, int **max, int **min )
{
    if( start == end )
    {
        *max = *min = start;
        return 0;
    }
    int *mid = start + ( end - start )/2;

    int *minLeft, *maxLeft;
    int leftDiff = getDiff( start, mid, &maxLeft, &minLeft );
    int *maxRight, *minRight;
    int rightDiff = getDiff( ( mid + 1 ), end, &maxRight, &minRight );

    *max = *maxLeft > *maxRight ? maxLeft : maxRight;
    *min = *minLeft < *minRight ? minLeft : minRight;

    int crossDiff = *maxLeft - *minRight;

    int maxDiff = leftDiff > rightDiff ? leftDiff : rightDiff;
    maxDiff = maxDiff > crossDiff ? maxDiff : crossDiff;

    return maxDiff;

}

// dp
int maxDiff2( int *num, unsigned length )
{
    // you should never forget this cornor case
    if( num == NULL || length < 2 )
    {
        return 0;
    }

    int *temp = ( int * )malloc( ( length - 1 ) * sizeof( int ) );
    // please notice the type coerce by putting ( int ) before ( length - 1 )
    // otherwise you would get : warning C4018: '<' : signed/unsigned mismatch
    for( int i = 0; i < ( int )( length-1 ); i++ )
    //or you could use 'unsigned' directly
    //for( unsigned i = 0; i < length-1; i++ )
    {
        *( temp + i ) = *( num + i ) - *( num + i + 1 );
    }

    int result  = getDiff2( temp, length - 1 );
    free( temp );

    return result;

}

int getDiff2( int *num, unsigned length )
{
    if( num == NULL || length < 1 )
    {
        return 0;
    }

    int max = 0, sum = 0;
    for( unsigned i = 0; i < length; i++  )
    {
        if( sum > 0 )
        {
            sum = sum + *( num + i );
        }
        else
        {
            sum = *( num + i );
        }
        if( max < sum )
        {
            max = sum;
        }
    }
    return max;
}

int maxDiff3( int *num, unsigned length )
{
    if( num == NULL || length < 2 )
    {
        return 0;
    }
    int *diff = ( int * )malloc( ( length - 1 ) * sizeof( int ) );
    *diff = *num - *( num + 1 );
    for( unsigned i = 2; i < length; i++ )
    {
        if( *( num + i -1 ) < *( num + i -1 ) + *( diff + i - 2 ) )
        {
            *( diff + i - 1 ) = *( num + i -1 ) + *( diff + i - 2 ) - *( num + i );
        }
        else
        {
            *( diff + i - 1 ) = *( num + i - 1 ) - *( num + i );
        }
    }
    int result =  *( diff + length - 2 );
    free( diff );
    return result;
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s