Array Applications (Finding Max/Min and Second Max/Min)

Learn about how we can find the maximum and minimum in an array.

We'll cover the following

Let’s see some examples to experience the practical usage of arrays.

Finding the maximum and minimum in an array

Let us solve first by finding the maximum number from the array.

Problem 1: Finding the maximum

As an example, we have written a program below with a given array of integers for finding the maximum number from the array.

A[] = {1 2 93 -4 75 6 8 23 }
Max: 93

The idea is simple:

  • We assume the first element to be the maximum number int max = A[0].
  • We traverse the array with an index variable ai=1 till the last entry at size-1.
    • We compare max with each element and update it whenever max is less than the A[ai].
#include <iostream>
using namespace std;
int main()
{
    int A[]={1,2,93,-4,75,6,8,23}; 
    int size = sizeof(A)/sizeof(int);   // sizeof(A) will be 8*4=32
                                        // sizeof(int) will be 4
    // Printing values using loop
    cout << "A[] = {";
    for(int i=0; i<size; i++)              
        cout << A[i]<<" ";
    cout << "}";
    
    int max = A[0];
    for(int ai=1; ai<size; ai++)
    {
        if(max<A[ai])    // If the new element is bigger then max
            max = A[ai]; // update the max with A[ai] 
    }
    cout << "\nMax: "<< max << endl;    // displaying the maximum
    
    return 0;
}

  • Line 7: The sizeof(A) will be the memory allocated to the array A[], 32 bytes, and sizeof(int) means 4. Hence, the size will be assigned the value of 8.

  • Line 15: The first value of the array A[0] is assigned to max. This is necessary because, if we don’t assign any value to max, it can have a garbage value. Then, in that case, inside the loop, it will be compared with a garbage value (which that can be greater than all the values inside the array). Similarly, we cannot assign max = 0 because all the values inside the array can be negative, and, in that case, max will not get updated. It will yield 0 as the maximum value, which will cause a logical error.

  • Lines 18–19: We compare the previously stored maximum (for an ai 'th iteration, max will be holding the maximum value out of the range A[0 ... ai-1], so the maximum from the first index 0 to the ai-1 index) and update it if the ai'th value is greater than max.

Exercise: Finding minimum in an array

Change the code above so that now the program should report the minimum in the array.

Problem 2: Finding the second maximum

To calculate the maximum and the second maximum number, we maintain two variables, max and secMax.

Here, we assume the first two elements to be the max and secMax. If the secMax is greater than the max, we swap the two values.

We then traverse the array from the third value, A[2], to the last value, A[size-1], and update the max and secMax values accordingly.

Let us look at the code and understand its working:

using namespace std;
#include <iostream>
int main()
{
    int A[8]={1,2,-93,-4,75,6,8,23}; 
    int size = sizeof(A)/sizeof(int);   
    
    cout << "A[] = {";
    for(int i=0; i<size; i++)              
        cout << A[i]<<" ";
    cout << "}";
    int max = A[0], secMax = A[1];
    if(max<secMax)
        swap(max, secMax);
    for(int ai=2; ai<size; ai++)
    {
        if(max<A[ai])
        {
            secMax = max;   // Shifting previous max to secMax
            max = A[ai];    // max should be updated with A[ai]
        }
        else if(secMax<A[ai]) // if the A[ai]'th value is 
                             //  not the maximum, still it 
                             //  can be second maximum i.e 
                             //  previous second maximum is < A[ai]
        {
            secMax = A[ai];
        }
    }
        
    cout << "\nMax: "<< max << endl; 
    cout << "Second Max: "<< secMax << endl;    
}

  • Line 19: If max is smaller than the new element A[ai], not only should max be updated by the new number, but the last max should also become the second maximum. Hence, first, we must update the second maximum and then the maximum (can you think of what would happen otherwise?).

  • Line 24: If max does not get updated, it is still possible that the new number is greater than the second maximum; if so, then we need to update the secMax with the new element A[ai].

We’ve seen how we can easily find the maximum and second maximum values in an array.

Practice Exercise: What do you think can be done to find the third maximum number? Change the code above in the playground above and test it.

Exercise: Finding the minimum and second minimum

Modify the code above so that the program should now print the minimum and second minimum of the array.