11

这是一道面试题：

在整数数组中找到最大可能的差异，使得较小的整数出现在数组的前面。

约束：数字不是唯一的。范围是java的整数范围。（或任何其他语言）

例子：

输入 1：{1, 100, 2, 105, -10, 30, 100}

最大的差异在 -10 和 100 -> 110 之间（这里 -10 位于第 5 个索引处，100 位于第 7 个索引处）

输入 2：{1、100、2、105、-10、30、80}

最大的差异在 1 和 105 -> 104 之间（这里 1 位于第 1 个索引处，105 位于第 4 个索引处）

可能的解决方案：

一种方法是检查所有可能的差异并跟踪迄今为止发现的最大差异 O(n^2) 复杂度。

这可以在 O(n^2) 时间内完成吗？

4

11 回答 11

11

Dhandeep 的算法很好，Vivek 将代码翻译成 Java 的工作！此外，我们还可以正常扫描数组，而不是反向扫描：

int seed[] = {1, 100, 2, 105, -10, 30, 100};
int maxDiff=Integer.MIN_VALUE, minNumber = Integer.MAX_VALUE;

for (int i = 0; i < seed.length ; i++){
    if(minNumber > seed[i]) 
       minNumber = seed[i];

    maxDiff = Math.max(maxDiff, (seed[i]-minNumber));
}
System.out.println(maxDiff);
于 2012-08-08T06:41:45.707 回答
10

从最后一个元素开始并向后移动。记住迄今为止发生的最大元素。对于每个元素，从最大值中减去并存储在相应的位置。

此外，您可以保留一个元素来存储最大差异并立即提供输出。O(n) 时间，O(1) 空间。

int max = INT_MIN;
int maxdiff = 0;

for (i = sizeof(arr) / sizeof(int) - 1; i >= 0; i--) {
  if (max < arr[i]) {
    max = arr[i];
  }
  int diff = max - arr[i];
  if (maxdiff < diff) {
    maxdiff = diff;
  }
}

print maxdiff;
于 2012-08-08T06:35:03.280 回答
4

感谢@Dhandeep Jain 的回答。有java版本：

//int seed[] = {1, 100, 2, 105, -10, 30, 100};
        int seed[] = {1, 100, 2, 105, -10, 30, 80};
        int maxDiff=Integer.MIN_VALUE, maxNumber = Integer.MIN_VALUE;

        for (int i = (seed.length-1); i >=0 ; i--){
            if(maxNumber < seed[i]) 
                maxNumber = seed[i];

            maxDiff = Math.max(maxDiff, (maxNumber - seed[i]));
        }
        System.out.println(maxDiff);
于 2012-08-08T06:52:08.170 回答
0

我建议最大的差异总是在那之前的最大数字和最小数字之间或之后的最小数字和最大数字之间。这些可以在线性时间内确定。

于 2012-08-08T06:38:54.947 回答
0 
public class Test{

    public static void main(String[] args){

        int arr1[] = {1,2,5,7,9};
        int arr2[] = {20,25,26,35};
        int diff = 0;
        int max = 0;

        for(int i=0;i<arr1.length;i++){
            for(int j=0;j<arr2.length;j++){

                diff =  Math.abs(arr1[i]-arr2[j]);
                if(diff > max){
                    max = diff;
                }
            }
        }
    System.out.println(max);
    }   
}
于 2013-10-07T11:20:22.497 回答
0 
    // Solution Complexity : O(n)   
    int maxDiff(int a[], int n){
        //  Find difference of adjacent elements
        int diff[n+1];
        for (int i=0; i < n-1; i++)
            diff[i] = a[i+1] - a[i];

        // Now find the maximum sum sub array in diff array
        int max_diff = diff[0];
        for (int i = 1 ; i < n-1 ; i++ ) {
            if( diff[i-1] > 0 ) diff[i] += diff[i-1];
            if( max_diff < diff[i] ) max_diff = diff[i];
        }
        return max_diff;
    }
于 2015-09-29T06:56:19.883 回答
0

首先找到数组相邻元素之间的差异，并将所有差异存储在大小为 n-1 的辅助数组 diff[] 中。现在这个问题变成了找到这个差数组的最大和子数组。

于 2016-03-20T07:14:38.207 回答
0

红宝石解决方案：

a = [3, 6, 8, 1, 5]
min = 10**6
max_diff = -10**6
a.each do |x|
  min = x if x < min
  diff = x - min
  max_diff = diff if diff > max_diff
end
puts max_diff
于 2017-03-08T02:43:27.460 回答
-1 
public static void findDifference(Integer arr[]) {
    int indexStart = 0;
    int indexMin = 0;
    int indexEnd = 1;
    int min = arr[0];
    int diff = arr[1] - arr[0];
    for (int counter = 1; counter < arr.length; counter++) {
        if (arr[counter] - min > diff) {
            diff = arr[counter] - min;
            indexEnd = counter;
            indexStart = indexMin;
        }
        if (arr[counter] < min) {
            min = arr[counter];
            indexMin = counter;
        }
    }
    System.out.println("indexStart = " + indexStart);
    System.out.println("indexEnd = " + indexEnd);
    System.out.println("diff = " + diff);
}
于 2016-07-30T20:06:29.013 回答
-1 
public static void findlargestDifference(int arr[]){

    int max_diff=0;     
    int min_value=Integer.MIN_VALUE;        
    for(int i=0;i<arr.length;i++){

        if(min_value<arr[i]){               
            min_value=arr[i];               
        }           
        int diff=min_value-arr[i];

        if(max_diff<diff){
            max_diff=diff;
        }                   
    }       
    System.out.println("Max Difference is  "+ max_diff);    
}
于 2018-08-17T09:35:55.670 回答
-2

我很确定这应该可以解决您的问题：

    int largestNumber = Integer.MIN_VALUE;
    int smallestNumber = Integer.MAX_VALUE; 

    for(int i = 0; i < yourArray.Length; i++)
    {
        if(yourArray[i] > largestNumber)
            largestNumber = yourArray[i];

        if(yourArray[i] < smallestNumber)
            smallestNumber = yourArray[i];

    }

    int biggestDifference = largestNumber - smallestNumber ;
于 2012-08-08T06:34:31.150 回答