Java – algorithm – the largest left sub array with smaller elements

I'm developing a program. I need to get the index of elements in the integer array, so that all elements on the right of the index are greater than all elements from 0 to the index position

For example:

Case: 1 – given the input – {5, - 2,3,8,6}, then I need the index position to be 2 (i.e. the array element value is 3) because all elements after index 2 are larger than all elements starting from index 0. Index 2 is {5,3}

Case: 2 – given the input – {- 5,6}, then I need an index position of 2 (i.e. array elements with a value of - 2), because all elements after index 2 are larger than {- 5, - 2} from index 0 to index 2

This 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,6 };
        int[] array2 = { -5,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,6]
index = 2,element = 3
[-5,6]
index = 0,element = -5

It applies to case 1, but case 2 fails You can help me solve this problem Is there a better way to solve this problem,

Solution

Unfortunately, your solution has several logical errors One counterexample: [2,1,6,5] (your algorithm returns index 1, but the answer is 2)

I propose another solution with O (n) time complexity:

>Iterate from left to right to calculate the maximum value of elements in [0.. I] interval. > Iteratively calculate the minimum value of the element in the [I 1.. n] interval from right to left, and compare the minimum value with the maximum value of the left element pre calculated in the first step

Example implementation:

static void process(int[] array) {
    int n = array.length;
    if (n < 2) return;

    int[] maxLeft = new int[n];
    maxLeft[0] = array[0];
    for (int i = 1; i < n; ++i) {
        maxLeft[i] = Math.max(maxLeft[i-1],array[i]);
    }  

    int minRight = array[array.length-1];
    for (int i = n-2; i >= 0; --i) {
        if (maxLeft[i] < minRight) {
            System.out.println("index = " + i + ",element = " + array[i]);
            return;
        } 
        minRight = Math.min(minRight,array[i]); 
    }
}

Runnable： http://ideone.com/mmfvmH