Finding the Largest Element in an Array


We are given an integer array of size N or we can say number of elements is equal to N. We have to find the largest/ maximum element in an array. The time complexity to solve this is linear O(N) and space compexity is O(1). Our efficient approach can be seen as the first step of insertion sort. In fact, this can be extended to find the k-th largest element which will take O(K * N) time and using this to sort the entire array will take O(N^2) time.If we have extra information, we can take its advantage to find the largest element in less time. For example, if array is already sorted, we can find the largest element in constant time O(1).

Efficient Approach

  • Firstly, program asks the user to input the values. So, user enter the size of array i.e. N and then enter the elements of array. Afterwards, program gives the output i.e. largest element in the entered array.
  • We assign the first element value to the temp variable.
  • Then we compare temp with all other elements inside a loop.
  • If the temp is larger than all other elements,
  • Then we return temp which store first element value as largest element.
  • But if the element is larger than the temp,
  • Then we store that element value into temp.
  • This way temp will always store the largest value.
  • Then we return temp.

Time complexity: O(N) where there are N elements in the array
Space complexity: O(1)

Pseudocode

Following is the pseudocode:

largest = array[i] // first element
for i from 1 to length(array):
    element_i = array[i]
    if largest < element_i
        largest = element_i
largest // this is our answer

Implementation

Following is the C++ implementation of our approach:

#include <iostream>
using namespace std;
    
int findlargestelement(int arr[], int n){
      int largest = arr[0];
   for(int i=0; i<n; i++) {
      if(largest<arr[i]) {
         largest=arr[i];
      }
   }
   return largest;
}
int main() {
   int n;
   cout<<"Enter the size of array: ";
   cin>>n; 
   int arr[n];
   cout<<"Enter array elements: ";
   for(int i=0; i<n; i++){
      cin>>arr[i];
   }
   int largest = findlargestelement(arr, n);
   cout<<"largest Element is: "<<largest;
   return 0;
}
Input:
Enter the size of array: 5
Enter array elements: 11 9 18 88 99
Output:
largest Element is: 99

Explanation

The program asks the user to enter the size of array and the elements of an array. Once all the elements are stored in the array, the function is called by passing array and function take array size as argument.

Firstly in the function we assign the value of first element to a variable and then we compare that variable value with every other element of array. If the variable is smaller than all other elements, then we return variable which store first element value as largest element. If any element is large than the variable then the value of that element is store into that variable and the loop continues until all the elements are traversed. This way we have the largest element in the variable at the end of the loop. Then we return value of the variable from the function.

Analysis

In this C++ Program to Find the Largest Number in an Array, the below For loop will iterate every cell present in a[4] array. Condition inside the for loops (i < Size) will ensure the compiler, not to exceed the array limit.

scanf statement inside the for loop will store the user entered values in every individual array element such as a[0], a[1], a[2], a[3]

for(int i=0; i<n; i++){
      cin>>arr[i];

The next, We assigned a[0] value to the Largest variable.

int largest = arr[0];

Next, We have one more for loop. It is for iterate each element in an array. If Statement inside it finds the largest Number in an Array by comparing each element in the array with the Largest value.If the element is larger than the largest number we have assigned we interchange the values.

 for(int i=0; i<n; i++) {
      if(largest<arr[i]) {
         largest=arr[i];

Example Explanation

a[4]={10,25,95,75};
largest=a[0];
  • First Iteration

The value of i will be 1, and the condition (i < 4) is True. So, it will start executing the statements inside the loop until the condition fails.

If statement (Largest < a[i]) inside the for loop is True because (10 < 25)
Largest = a[i] => a[1]
Largest = 25

  • Second Iteration

The value of i will be 2, and the condition (2 < 4) is True.

If statement (Largest < a[2]) inside the for loop is True because (25 < 95)
Largest = a[2]
Largest = 95

  • Third Iteration

The value of i will be 3, and the condition (3 < 4) is True.

If statement (Largest < a[3]) inside the for loop is False because (95 < 75). So, the largest value will not be updated. It means
Largest = 95

  • Fourth Iteration

After the incrementing the value of i, i will become 5, and the condition (i < n) will fail. So, it will exit from the loop.

The below cout statement is to print the Largest Number inside an Array. In this example, it is 95.

cout<<"largest Element is: "<<largest;

Question

Are the array elements necessarily positive?
Yes,There can be only non negative numbers
No
Yes
No,but can't be zero
No, they can be positive, negative, or zero

With this article at OpenGenus, you must have the complete idea of the algorithm to find the largest element in a set of elements. Enjoy.