java 在较小的整数出现较早的情况下，找出数组中可能的最大差异
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/11858790/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the largest possible difference in an array with the smaller integer occurring earlier
提问by Vivek
This is an interview question:
这是一道面试题：
Find the largest possible difference in an array of integers, such that the smaller integer occurs earlier in the array.
在整数数组中找出最大可能的差异，使得较小的整数在数组中出现得更早。
Constraint: Numbers are not unique. The range is Integer range of java. (or any other language)
约束：数字不是唯一的。范围是java的整数范围。（或任何其他语言）
Example:
例子：
input 1: {1, 100, 2, 105, -10, 30, 100}
输入 1: {1, 100, 2, 105, -10, 30, 100}
The largest difference is between -10 and 100 -> 110 (here -10 is at the 5th index and 100 is at 7th index)
最大的差异是在 -10 和 100 -> 110 之间（这里 -10 在第 5 个索引处，100 在第 7 个索引处）
input 2: {1, 100, 2, 105, -10, 30, 80}
输入 2: {1, 100, 2, 105, -10, 30, 80}
The largest difference is between 1 and 105 -> 104 (here 1 is at the 1st index and 105 is at 4th index)
最大的差异是在 1 和 105 -> 104 之间（这里 1 在第 1 个索引处，105 在第 4 个索引处）
Possible Solution:
可能的解决方案：
One approach is check for all possible differences and keep a track of the biggest difference found till now O(n^2) complexity.
一种方法是检查所有可能的差异并跟踪迄今为止发现的最大差异 O(n^2) 复杂度。
can this be done in better than O(n^2) time?
这可以在比 O(n^2) 时间更好的时间内完成吗？
采纳答案by Dhandeep Jain
Start from the last element and move backwards. keep in memory the largest element occurred till now. for each element subtract from the max and store at the respective position.
从最后一个元素开始向后移动。将迄今为止发生的最大元素保存在内存中。对于每个元素从最大值中减去并存储在各自的位置。
Also, you can keep an element to store the max difference and give the output straight away. O(n) time, O(1) space.
此外，您可以保留一个元素来存储最大差异并立即提供输出。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;
回答by alfasin
Dhandeep's algoritm is good and Vivek's translation of the code to Java works! Also, we can also scan the array normally and not in reverse:
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);
回答by Vivek
Thanks @Dhandeep Jain for the answer. There is the java version:
感谢@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);
回答by Ankit Jain
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);
}
}
回答by Rezwan4029
// 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;
}
回答by SMohan
First find the difference between the adjacent elements of the array and store all differences in an auxiliary array diff[] of size n-1. Now this problems turns into finding the maximum sum subarray of this difference array.
首先找出数组相邻元素之间的差异，并将所有差异存储在大小为 n-1 的辅助数组 diff[] 中。现在这个问题变成了寻找这个差分数组的最大和子数组。
回答by themel
I propose that the largest difference is always between the largest number and the smallest number before that or between the smallest number and the largest number after that. These can be determined in linear time.
我建议最大的差异总是在它之前的最大数和最小数之间，或者在其后的最小数和最大数之间。这些可以在线性时间内确定。
回答by Soheil
Ruby solution:
红宝石解决方案：
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
回答by apachauri
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);
}
回答by Rajesh Kumar
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);
}
