Посчитать способы разделить список так, чтобы слева все числа были меньше, чем справа

Question

Необходимо разделить список из произвольного количества чисел таким образом, чтобы слева все числа были меньше, чем справа. И посчитать количество таких способов.

То есть, например, [3,2,3,5,8,7,9] можно разделить тремя способами:

[3,2,3]  и [5,7,6,9]
[3,2,3,5] и [8,7,9]
[3,2,3,5,8,7] и [9]

Понимаю, как это сделать с помощью вложенного цикла, но нужно, чтоб было именно O(n).

Answer 1

Tо есть для каждого элемента i вам надо найти максимальный элемент среди [0, i] и минимальный элемент среди [i+1, N] и проверить, что максимальный слева меньше, чем минимальный справа. Это делается за линейное время без проблем, надо только иметь 2 доп массива для максимальных и минимальных элементов.

Код на C#

var input = new[] { 3, 2, 3, 5, 8, 7, 9 };
var maxes = new int[input.Length];
var mins = new int[input.Length];

maxes[0] = input[0];
for (int i = 1; i < input.Length; i++)
    maxes[i] = Math.Max(maxes[i - 1], input[i]);

mins[mins.Length - 1] = input[input.Length - 1];
for (int i = input.Length - 2; i >= 0; i--)
    mins[i] = Math.Min(mins[i + 1], input[i]);

int count = 0;
for (int i = 0; i < input.Length - 1; i++)
    if (maxes[i] < mins[i + 1]) count++;

Console.WriteLine(count);

Answer 2

Не представляю как это за O(n) сделать.

n = [3, 2, 3, 5, 8, 7, 9]

for i in range(1, len(n)):
    if max(n[:i]) < min(n[i:]):
        print(n[:i], n[i:])

БЛОГ НА HUSL

Посчитать способы разделить список так, чтобы слева все числа были меньше, чем справа

Ответы (2 шт):