Как я могу найти самый длинный подмассив с максимальной разницей 0 и 1 с временем O(n) и пробелом O(1)

Question

Как я могу найти самый длинный вложенный массив с максимальной разницей 0 и 1 с временной сложностью O(n) и пространством O(1)? Заранее спасибо за отзывы и решения!

Например: входной массив равен {3, 3, 4, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7} и вывод должен быть примерно таким: начальный индекс равен 6 с длиной 7.

Другой пример: входной массив {5, 5, 5, 5, 3, 3, 2, 2, 1} и выход: индекс 0 и длина 4.

Возможное решение: я использую вложенные циклы для var i и var j

Answer 1

Вы не имеете права копировать это и использовать его для своего задания, но оно должно дать вам представление о том, как это сделать.

class Find {
    public static void main(String args[]) {
        int parent[][] = {
            {1,2,3,4},
            {8,7,6,5,8},
            {9,8},
            {8,7,6,5,8,0,0,0,9,9,9},
            {8}
        };

        int max = parent[0].length;
        int i = 0;//CONSTANT SPACE O(1)
        //LINEAR TIME O(n)
        for (int j = 1; j < parent.length; j++) {
            if (parent[j].length > max) {
                max = parent[j].length;
                i = j;
            }
        }

        System.out.println("Longest sub-array index: " + i);
    }
}

Я могу накормить тебя на сегодня, но ты должен изучить этот материал и накормить себя на всю жизнь...