Java Program to Find Local Maxima in an Array

This is the Java Program to Find Local Maximas in an Array.

Problem Description

Given an array of integers, find out the local maxima present in the array.
An element in an array is a local maxima if it greater than the element after it, and the element before it.
For the elements at the extreme end only one check is required, that is, the element following the first element or the element before the last element.
In case of two or more maxima, only one of them is returned.

Example:
Array = [1, 2, 3, 4, 5, -1]

Output:
5

Problem Solution

The idea here is to use an algorithm, similar to the binary search. Check the middle element of the array, if it is greater than the elements following it and the element preceding it, then it is the local maxima, else if it is greater than the preceding element, then the local maxima is in the left half, else the local maxima is in the right half.

Program/Source Code

Here is the source code of the Java Program to Find Local Maximas in an Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

```
 
```

//Java Program to Find Local Maximas in an Array

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class LocalMaxima {
```

    // Function to return the index of the local Maxima

    static int localMaxima(int[] array){

```
        int low,mid,high;
```
```
        low = 0;
```
```
        high = array.length-1;
```
```
        int ans;
```
```
        while(low<=high){
```
```
            mid = (low + high)/2;
```

            if((mid == 0 || array[mid-1] < array[mid])

                && (mid == array.length-1 || array[mid+1] < array[mid])){

```
                return mid;
```
```
            }
```

            else if(mid > 0 && array[mid-1] > array[mid]){

```
                high = mid-1;
```
```
            }
```
```
            else{
```
```
                low = mid+1;
```
```
            }
```
```
        }
```
```
        return -1;
```
```
    }
```
```
 
```
```
    // Function to read input
```

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
                return;
```
```
            }
```
```
        }
```
```
        int index = localMaxima(array);
```

        System.out.println("The local maxima is " + array[index]);

```
    }
```
```
}
```

Program Explanation

1. In the function localMaxima(), we initialize two variables high and low as array.length-1 and 0 respectively.
2. Using a loop while(low <=high), we first calculate the middle index.
3. Now, in the condition if((mid == 0 || array[mid-1] < array[mid]) && (mid == array.length-1 || array[mid+1] < array[mid])), we check whether the element at current middle index is a maxima.
4. If the element is a maxima, then we return the current middle index, otherwise using the condition else if(mid > 0 && array[mid-1] > array[mid]), we first check that we are not at the beginning of the array and finally, check if the preceding element is greater than the current middle element.
5. If it is, we then set high to mid-1, to look in the first half of the array. Otherwise, we set low to mid+1 to look for the maxima in the second half of the array.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

Time Complexity: O(log(n)) where n is the number of elements in the array.

Runtime Test Cases

 
Case 1 (Positive test case - local maxima is not at the extreme ends):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
-1
The local maxima is 5
 
Case 2 (Positive test case - local maxima is at the beginning of the array):
 
Enter the size of the array
8
Enter array elements
8
7
6
5
4
3
2
1
The local maxima is 8 
 
Case 3 (Positive test case - local maxima is at the end of the array):
 
Enter the size of the array
6
Enter array elements
1
2
3
4
5
6
The local maxima is 6

Recommended Articles: