Каково количество подмассивов, которые будут включать определенный индекс «i»?

Question

Рассмотрим массив из 'n' элементов, где i - это элемент с индексом i , где 1 <= i <= N. Мне нужно посчитать количество подмассивов (смежных подпоследовательностей массива), которые будут включать определенный индекс <em>i . Например, рассмотрим, A = [1,2,3,4,5] Элемент 2 с индексом 2 , будет включен в 8 подмассивов - {2}, {1,2}, {2,3}, {1,2,3}, {2,3,4}, {1,2,3,4}, {2,3,4,5}, {1,2,3,4 , 5}.

Есть ли способ создать формулу для этого с точки зрения размера массива n и выбранного индекса i ?

Answer 1

Количество последовательностей, включая индекс i, будет равно количеству последовательностей слева от i умноженного на число справа. Для левого и правого мы должны включить пустую последовательность.

В вашем примере это будет:

left: {}, {1}
right: {}, {3}, {3,4}, {3,4,5}

Сопряжение каждой левой последовательности с каждой правой последовательностью, с i в центре, очевидно, дает вам 8 подмассивов в вашем примере , (Если вы рассматриваете левую и правую части выше как наборы, то вы хотите сформировать декартово произведение ).

Число левых последовательностей равно i, число справа n-i+1 Таким образом, общая сумма составляет i*(n-i+1).