How do I find the biggest difference in an array?

If I have an array, and I have to find the biggest difference, but the smallest element HAS to be before the biggest element, what do I do?

[madhan ravi]

AN EXAMPLE?

[AelinAG]

[62 1 18] The biggest difference is here 61, but since the smallest element goes first the solution would be 17

[madhan ravi]

You mean the difference between the two elements 1 and 18 because we just ignore the max value ?

Answer 1

[Paolo]

>> A=[62 1 0];
>> max(reshape((diff(perms(A))),1,[]))
62

>> A = [62, 10, 18, 100, 4, -300];
>> max(reshape((diff(perms(A))),1,[]))
400

Answer 2

[Matt J]

If only consecutive differences are to be considered,

 A=[62 1 18];

 diffs= diff(A);

 result=max( diffs(diffs>=0) )

EDIT :

If they can be non-consecutive,

diffs=triu( A(:).'- A(:) );
 result=max( diffs(diffs>=0) )

[Image Analyst]

What if the largest difference does not occur with immediately adjacent elements?

[Matt J]

I'm guessing that the OP is interested in consecutive differences only, but if not, it's a simple modification,

diffs=triu( A(:).'- A(:) );
result=max( diffs(diffs>=0) );

[Paolo]

A = [62, 10, 18, 100, 4, -300];
diffs=triu( A(:).'- A(:) );
result=max( diffs(diffs>=0) )

returns 90 instead of 400

[Matt J]

90 is correct. Not 400. Remember, allowable differences A-B are those in which B precedes A in the list.

[Paolo]

Ah yes that is what OP is asking for, read Image Analyst's comment and got confused

Answer 3

[Image Analyst]

The code below will work even if the biggest difference is not in adjacent elements, and if the values are negative.

A = [62, 10, 18, 100, 4, -300];
% The biggest difference is between element 4 and 6 and has a distance of 400.
distances = pdist2(A', A')
maxDistance = max(distances(:))
[rows, columns] = find(distances == maxDistance)
index1 = rows(1);
index2 = columns(1);
% Swap if necessary
if index1 > index2
  [index1, index2] = deal(index2, index1)
end
message = sprintf('The biggest difference is between\nelement #%d (%f) and\nelement #%d (%f)\nwith a difference of %f',...
  index1,  A(index1), index2,A(index2), A(index1)-A(index2));
fprintf('%s\n', message);
uiwait(helpdlg(message));

You'll see

distances =
     0    52    44    38    58   362
    52     0     8    90     6   310
    44     8     0    82    14   318
    38    90    82     0    96   400
    58     6    14    96     0   304
   362   310   318   400   304     0
maxDistance =
   400
rows =
     6
     4
columns =
     4
     6
index1 =
     4
index2 =
     6
The biggest difference is between
element #4 (100.000000) and
element #6 (-300.000000)
with a difference of 400.000000

It uses pdist2() in the Statistics and Machine Learning Toolbox to compute the difference of every element from every element (including itself).

[Ruben Lange]

Thanks for the useful code. I was wondering though, if you could do the same but then to find the minimum distance between every entry and a constant. Its kind of hard to explain but here is an example:

You have a vector [2, 8, 15, 11, 31], and a constant 2. Now I want to find which two elements when substracted from eachother, are closest to this constant. In this example this would be 11-8 = 3, which is the difference that is closest to 2, but in the actual code it should also consider the difference between every entry in this array. Also, in my problem, it might come up that two entries both have the same distance, and therefore are both closest to 2. If it is possible it would be the nicest if you would get a sorted list with the best fitting elements.

I hope you understand what I mean. Thanks in advance for any help!

[Image Analyst]

This works:

targetValue = 3;
v = [2, 8, 15, 11, 31]
numElements = numel(v)
distances = pdist2(v(:), v(:))
% Subtract the target value and we'll want to look for values closest to 0.
d2 = distances - targetValue
% Now we don't want 0 which is just the distance between an element and itself.
% So tell it not to look at the diagonal.
validIndexes = ~eye(numElements)
% Find the min for non-diagonal pairs.
d2 = distances(validIndexes)
minDistance = min(d2) % Find the min
% List values where it's the target value.
[rows, columns] = find(distances == minDistance)
for k = 1 : length(rows)/2
	fprintf('%d and %d have a difference of %d.\n', v(rows(k)), v(columns(k)), minDistance);
end

You'll see:

v =

2 8 15 11 31

numElements =

5

distances =

0 6 13 9 29

6 0 7 3 23

13 7 0 4 16

9 3 4 0 20

29 23 16 20 0

d2 =

-3 3 10 6 26

3 -3 4 0 20

10 4 -3 1 13

6 0 1 -3 17

26 20 13 17 -3

validIndexes =

5×5 logical array

0 1 1 1 1

1 0 1 1 1

1 1 0 1 1

1 1 1 0 1

1 1 1 1 0

d2 =

6

13

9

29

6

7

3

23

13

7

4

16

9

3

4

20

29

23

16

20

minDistance =

3

rows =

4

2

columns =

2

4

11 and 8 have a difference of 3.

Answer 4

[Image Analyst]

If you want to find the biggest difference in the upwards direction only, ignoring any differences in the downward direction (where the index of the bigger value is less than the index of the smaller value), and want to allow elements that don't need to be adjacent to each other, this code will work:

% Make vector where biggest difference in the upwards direction is between index 2 and 6.
% Note there is a bigger difference in the downward direction 
% between elements 5 and 6, but we don't care about that.
A = [130, 85, 110, 100, 115, 80, 105]
plot(A, 'b*-', 'LineWidth', 2, 'MarkerSize', 14);
grid on;
xlabel('Index', 'FontSize', 20);
ylabel('Value', 'FontSize', 20);

[rows, columns] = size(A)
for row = 1 : length(A)
  for col = 1 : length(A)
    distances(row, col) = A(row) - A(col);
  end
end
distances % Print to command window.
% Consider only positive differences
distances = tril(distances)
maxDistance = max(distances(:))
[rows, columns] = find(distances == maxDistance)
index1 = rows(1);
index2 = columns(1);
% Swap if necessary
if index1 > index2
  [index1, index2] = deal(index2, index1)
end
% Put a circle around the pair we found on the plot.
hold on;
plot([index1, index2], [A(index1), A(index2)], 'ro', 'MarkerSize', 20, 'LineWidth', 2);
message = sprintf('The biggest difference is between\nelement #%d (%.1f) and\nelement #%d (%.1f)\nwith a difference of %.1f',...
  index1,  A(index1), index2,A(index2), A(index2)-A(index1));
fprintf('%s\n', message);
uiwait(helpdlg(message));

Note how it finds elements 2 and 5 with a difference of 30 even though elements 5 and 6 have a difference of 35, but the bigger value occurs at index 5, which comes before the index of the smaller value at index 6, so I ignore that pair.