Find a pair of maximum differences in an array

Question

I am working on some kata, but I can not pass all the test cases.

So the situation is this:

For any array, such as this array:, int[] a = {2, 3, 10, 2, 4, 8, 1}find the pair of max differences in the array, in the meantime, make sure that a higher index has a higher value than a smaller value.

In this example: 10is the largest element, 1is the smallest because it 10is in the index 2, 1has an index 6, so it is not taken into account, since a higher pair has a lower index. So the correct answer is a[0]and a[2], max different - 10-2.

Another requirement is the size of the array Nbetween 1and 1_000_000, any given a[i]is between -1_000_000and1_000_000

I wrote the code as follows:

static int maxDifference(int[] a) {
    //test array size
    if (a.length < 1 || a.length > 1_000_000) return -1;

    int[] oldArr = Arrays.copyOf(a, a.length);
    Arrays.sort(a);
    int max = a[a.length - 1];
    if (max > 1_000_000 || a[0] < -1_000_000) return -1;

    int min = max;
    for (int i = 0; i < oldArr.length; i++) {
        if (oldArr[i] < max) {
            min = Math.min(min, oldArr[i]);
        }
        if (oldArr[i] == max) break;
    }
    int result = min == max ? -1 : max - min;
    return result;
}

My logic pretty much makes a copy of the array, and then sorts the array and then loops through it, keeping a pointer to the max and min values, and then I get the result.

What bothers me, I only know that there are some test cases that I did not pass, but no hints as to why this did not pass. Can someone give me some advice and what can I lose in this helper method?

Answer 1

, , , :

static int maxDifference(int[] a) {
    int minimum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
    // depending on interpretation of requirements, above line might be wrong
    // Instead, use:
    // return diff > 0 ? diff : -1;
}

Answer 2

( , , , , ), , :

public static int maxDifference(int[] a) {
    long bounds = 1_000_000;

    int biggestDifference = -1;
    if(a.length > bounds){
        return -1;
    }
    for (int i = 0; i < a.length-1; i++) {
        if(Math.abs(a[i]) > bounds){
            return -1;
        }
        for (int j = i+1; j < a.length; j++) {
            int difference = Math.abs(a[j] - a[i]);
            if(difference > biggestDifference){
                biggestDifference = difference;
            }
        }
    }
    return biggestDifference;
}

Answer 3

.

import java.util.Arrays;

public class MaxDifference {
    private static long difference(
            final int[] array,
            final int minPos,
            final int maxPos
    )
    {
        assert( minPos < maxPos );
        assert( array[minPos] < array[maxPos] );
        return ( (long) array[maxPos] ) - ( (long) array[minPos] );
    }

    public static int[] maxDifference( final int[] array ){
        if ( array == null|| array.length < 2 )
            return null;

        // Position of global minima.
        int minimaPos                 = 0;
        // Value of global minima.
        int minimaValue               = array[0];
        // Position of minima for current maximum difference.
        int minimaPosForMaxDifference = 0;
        // Position of maxima for current maximum difference.
        int maximaPosForMaxDifference = -1;
        // Current maximum difference.
        long maxDifference            = -1;
        // Current position
        int pos                       = 0;


        while ( pos < array.length - 1 ){
            // Find the local minima
            while( pos < array.length - 1 && array[pos] > array[pos + 1])
            {
                pos++;
            }
            // Test if the local minima is the current global minima.
            if ( array[pos] < minimaValue )
            {
              minimaPos   = pos;
              minimaValue = array[pos];
            }

            // Find the local maxima
            while( pos < array.length - 1 && array[pos] <= array[pos + 1])
            {
                pos++;
            }

            if ( pos > minimaPos )
            {
                long diff = difference( array, minimaPos, pos );
                if ( diff > maxDifference )
                {
                    minimaPosForMaxDifference = minimaPos;
                    maximaPosForMaxDifference = pos;
                    maxDifference   = diff;
                }
            }

        }
        if ( maximaPosForMaxDifference == -1 )
            return null;

        return new int[]{ minimaPosForMaxDifference, maximaPosForMaxDifference };
    }

    public static String toDiffString( final int[] array ){
        final int[] diff = maxDifference( array );
        if ( diff == null )
            return String.format(
                    "%s has no maximum difference",
                    Arrays.toString(array)
            );
        else
            return String.format(
                    "%s has maximum difference of %d at %s",
                    Arrays.toString(array),
                    difference( array, diff[0], diff[1] ),
                    Arrays.toString( diff )
            );
    }
    public static void main( final String[] args ){
        System.out.println( toDiffString( new int[]{} ) );
        System.out.println( toDiffString( new int[]{ 0 } ));
        System.out.println( toDiffString( new int[]{ 0, 0 } ));
        System.out.println( toDiffString( new int[]{ 1, 0 } ));
        System.out.println( toDiffString( new int[]{ 2, 1, 0 } ));
        System.out.println( toDiffString( new int[]{ 0, 1, 2 } ));
        System.out.println( toDiffString( new int[]{2, 3, 10, 2, 4, 8, 1} ));
        System.out.println( toDiffString( new int[]{5,0,3,1,4} ));
        System.out.println( toDiffString( new int[]{5,0,3,-1,4} ));
        System.out.println( toDiffString( new int[]{ Integer.MIN_VALUE, Integer.MAX_VALUE } ));
    }
}

:

[] has no maximum difference
[0] has no maximum difference
[0, 0] has maximum difference of 0 at [0, 1]
[1, 0] has no maximum difference
[2, 1, 0] has no maximum difference
[0, 1, 2] has maximum difference of 2 at [0, 2]
[2, 3, 10, 2, 4, 8, 1] has maximum difference of 8 at [0, 2]
[5, 0, 3, 1, 4] has maximum difference of 4 at [1, 4]
[5, 0, 3, -1, 4] has maximum difference of 5 at [3, 4]
[-2147483648, 2147483647] has maximum difference of 4294967295 at [0, 1]

Answer 4

, Amit , . , , , (Math.Max). Unit test . , O (n).

//using minimum (Amit solution - vote him up!)
static int maxDifferenceWithMin(int[] a) {
    int minimum, diff = -1;
    if (a.length == 0) {
        return -1;
    }
    minimum = a[0];
    for (int i = 1; i < a.length; i++) {
        diff = Math.max(diff, a[i] - minimum);
        minimum = Math.min(minimum, a[i]);
    }
    return diff;
}

//using maximum
static int maxDifferenceWithMax(int[] a) {
    int maximum, diff = -1;
    if(a.length == 0) {
        return -1;
    }
    maximum = a[a.length - 1];
    for (int i = a.length - 1; i >= 0; i--) {
        diff = Math.max(diff, a[i] - maximum);
        maximum = Math.max(maximum, a[i]);
    }
    return diff;
}

Answer 5

    static int MaxDiff(int[] inputArr)
    {
        int n = inputArr.Length;
        if (n < 1) return -1;
        int max = 0;
        int result = 0;
        int result2 = 0;
        for (int i = 1; i < inputArr.Length-1; i++)
        {
            if (inputArr[i] > inputArr[i - 1])
                max = inputArr[i];
            else
                continue;
            for (int j = i; j > 0; j--)
            {
                result2 = max - inputArr[j - 1];
                if(result2 > result)
                     result = max - inputArr[j - 1];
            }
        }
        return result;
    }

    static void Main(string[] args)
    {
        int[] inputArr = { 7,2,3,10,2,4,8,1 };
        Console.Write("Maximum Differnce is " + MaxDiff(inputArr));
    }

8

Answer 6

, , - .
:

    int n = in.readInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
        arr[i] = in.readInt();
    }
    int max = arr[n-1];
    int diff = 0;
    for(int i=n-1;i>=0;i--){
        if(arr[i] > max)
            max = arr[i];
        else{
            diff = Math.max(diff, max-arr[i]);
        }
    }
    out.print(diff);

, . , ( ). , ( ). .

Answer 7

:

Arrays.sort(this.elements);
maximumDifference = this.elements[this.elements.length-1] - this.elements[0];