How to find the maximum difference of an array and print the numbers that gave the difference?

Question

I've been trying to get into coding and need some help with my code. I figured out how to get the maximum difference, but I also want to print the numbers used to get that difference. For example, a-b=diff, I want to print a, b, and diff separately. My friend also challenged me to get the smaller value first, then get the bigger value. Now, once I pick a certain element in the array as the smallest number, I'm only allowed to pick through the next elements for the biggest number. For example, if the array is {2, 3, 4, 15, 8, 1}, it should be 15 - 2, not 15 - 1.

Here is my code to get the maximum difference/what I have so far:

#include <iostream>
using namespace std;
 
int maximum_difference(int arr[], int n)
{    
  int max_num = arr[1];
  int min_num = arr[0];
  int max_difference = max_num - min_num;
  
  for (int i = 0; i < n; i++)
  {
    for (int j = i+1; j < n; j++)
    {    
      if (arr[j] - arr[i] > max_difference)
      {
        max_num=arr[j];
        min_num=arr[i];
        max_difference = max_num - min_num;
      }
    }
  }        
  return max_difference;
}
 

int main()
{
  int n;
  cout<<"elements: ";
  cin >> n;

  int arr[n];
  for(int i=0; i<n; i++)
    {
      cin >> arr[i];
    }
  
  cout << "Maximum difference is " << maximum_difference(arr, n);
 
  return 0;
}

What should I add or replace, so that I could cout max_num and min_num together with the max_difference?

Answer 1

You don't need to use two for loops for finding the max and min values of the array. Additionally, in Standard C++ the size of an array must be a compile-time constant. So when you wrote:

int n;
cin >> n;
int arr[n]; //NOT STANDARD C++

The statement int arr[n]; is not standard C++ since n is not a constant expression.

Better would be to use std::vector as shown below:

Method 1: Manually finding max and min values

#include <iostream>
#include <vector>
#include <climits>
 
//this function take a vector as input and returns the difference b/w max and min values 
int maximum_difference(const std::vector<int>& arr)
{    
  int max_num = INT_MIN;
  int min_num = INT_MAX;
  
  //iterate through the vector to find the max and min value 
  for(const int& element: arr)
  {
      if(element >  max_num)
      {
          max_num = element;
      }
      if(element < min_num)
      {
          min_num = element;
      }
  }
  return max_num - min_num; //return the difference of mx and min value
}
 

int main()
{
  int n;
  std::cout<<"elements: ";
  std::cin >> n;

  //create vector of int of size n 
  std::vector<int>  arr(n);
  
  //take elements from user
  for(int i=0; i<n; i++)
  {
    std::cin >> arr[i];
  }
  
  std::cout << "Maximum difference is " << maximum_difference(arr);
 
  return 0;
}

Method 2: Using std::minmax_element to find the max and min values

Here we use std::minmax_element which returns a pair consisting of an iterator to the smallest element as the first element and an iterator to the greatest element as the second.

#include <iostream>
#include<vector>
#include<algorithm>
int main()
{
    int n;
    std::cout<<"elements: ";
    std::cin >> n;

    //create vector of int of size n 
    std::vector<int>  arr(n);
  
    //take elements from user
    for(int i=0; i<n; i++)
    {
       std::cin >> arr[i];
    }
    auto it = std::minmax_element(arr.begin(), arr.end()); 
    std::cout << "The max difference is " << *it.second - *it.first;
    return 0;
}

Answer 2

Does it help?

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

int maximum_difference(int arr[], int n)
{    
//Init to same number
int max_num = arr[0];
int min_num = arr[0];
int difference;

//Find max and min by single traverse
 for (int j = 1; j < n; j++)
 {
   if (max_num < arr[j]) 
   {
     max_num = arr[j];
   }
   if(min_num > arr[j])
   {
     min_num = arr[j];
   }
 }
 /*
 |----.--.--.--.--.--.--.--|
 |..-3  -2  0  1  2  3  .. | 
 */
 if( max_num >= 0 && min_num >= 0)   //both are +ve numbers
    difference = max_num - min_num;
 else if(max_num > 0 && min_num < 0) //max is positve and min is negative
    difference = max_num + abs(min_num);
 else                                //both are -negative
    difference = abs(abs(max_num) - abs(min_num)); //abs value is the difference between max and min     

return difference;
}


int main()
{
 int n;
 int arr[100];
 printf("How many elements: ");
 scanf("%d", &n);
 
 //validate
 if(n == 0 || n < 0)
    printf("Enter valid number in 1..100");
 if(n >100)
    printf("The program can parse 100 elements at Maximum. Enter 1..100");
 
 //read inputs
 printf("\nEnter the integers: ");
 for(int i=0; i<n; i++)
 {
   scanf("%d", &arr[i]);
 }
 
 //display difference
 printf("\nMaximum difference is %d", maximum_difference(arr, n));
 
 return 0;
}

Answer 3

I will address the algorithm part of this. The C++ part doesn't interest me; once you see the solution you'll know why.

We must choose indices i and j such that i <= j and a[j] - a[i] is maximized.

Your example sequence:

a = [2, 3, 4, 15, 8, 1]

Find the incremental maximum values starting from the right. (Most readers will immediately get the rest of the solution given this one hint).

maxs = [15, 15, 15, 15, 8, 1]

Find the incremental minimum values starting from the left.

mins = [2, 2, 2, 2, 2, 1]

Subtract them to find the greatest possible differences.

diffs = [13, 13, 13, 13, 6, 0]

The maximum element in this array, 13 is the largest value of a[j] - a[i] possible.

To find the actual values of i and j we store the indices of our best value for i and indices for the corresponding best value for j.

bestj = [3, 3, 3, 3, 4, 5]
besti = [0, 0, 0, 0, 0, 5]

We can compute the best difference the same way as before, but indirectly via the indices. For each k, diffs[k] = a[bestj[k]] - a[besti[k]] which still produces the same diffs as before:

diffs = [13, 13, 13, 13, 6, 0]

And when we find the index of the maximum diff, any such index will do. There may be multiple solutions, but this will find one solution (values for i and j) that produces a maximal result. Suppose we identify index k as having the maximal value 13, theni = besti[k] and j = bestj[k].

And therefore one solution is i = 0 and j = 3.

confirm:

a = [2, 3, 4, 15, 8, 1]
     ^i       ^^j

i = 0
j = 3
a[i] = 2
a[j] = 15
a[j] - a[i] = 13

So again, I'm not going to provide the code, but if you can write a loop to scan from right to left computing incremental maximums as you go (as shown above), then you can code it up easily.