Algorithm - Maximum left sub-array with lesser elements

Viewed 261

I am working on a program where I need to get the index of element in an array of integers such that all elements to the right of the index are greater than all the elements from 0 to that index position.

For example:

Case : 1 - Given input - { 5, -2, 3, 8, 6 } then I need the index position as 2 (i.e array element with value 3) because all elements after index 2 are greater than all elements starting from index 0 to index 2 i.e {5,-2,3}

Case : 2 - Given input - { -5, 3, -2, 8, 6 } then I need the index position as 2 (i.e array element with value -2) because all elements after index 2 are greater than all elements starting from index 0 to index 2 i.e {-5,3,-2}

Here is my Java program:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ArrayProgram {

    public static void main(String[] args) {
        int[] array1 = { 5, -2, 3, 8, 6 };
        int[] array2 = { -5, 3, -2, 8, 6 };
        process(array1);
        process(array2);
    }

    private static void process(int[] array) {
        List<Integer> list = new ArrayList<Integer>();
        int maxIndex = 0;
        list.add(array[0]);
        System.out.println(Arrays.toString(array));
        for (int i = 1; i < array.length; i++) {
            if (array[i] <= Collections.max(list)) {
                list.add(array[i]);
                maxIndex = i;
            }
        }

        System.out.println("index = " + maxIndex + ", element = " + array[maxIndex]);
    }
}

The program output is :

[5, -2, 3, 8, 6]
index = 2, element = 3
[-5, 3, -2, 8, 6]
index = 0, element = -5

It works for case 1 but fails for case 2. Can you please help me in fixing this. Is there any other better way to solve this,

3 Answers
Related