Нахождение наибольшего из каждого подмассива длины k

Question

Вопрос для интервью: - Для данного массива и целого числа k найдите максимум для каждого смежного подмассива размера k.

Sample Input :

1 2 3 1 4 5 2 3 6 

3 [ value of k ]


Sample Output :
3
3
4
5
5
5
6

Я не могу придумать ничего лучше, чем грубая сила. В худшем случае это O (nk), когда массив сортируется в порядке убывания.

Answer 1

Вы можете сделать это за O (n) время с O (n) пробелом.

Разделить массив на блоки каждого.

[a1 a2 ... ak] [a(k+1) ... a2k] ...

Для каждого блока сохраните еще два блока, левый блок и правый блок.

i-й элемент левого блока будет максимальным из элементов i слева. Элемент ith правого блока будет максимальным из элементов i справа.

У вас будет два таких блока для каждого блока k.

Теперь, если вы хотите найти максимум в диапазоне a[i... i+k], скажем, элементы охватывают два из указанных выше блоков k.

[j-k+1 ... i i+1 ... j] [j+1 ... i+k ... j+k]

Все, что вам нужно сделать, это найти максимум RightMax, равный i to j первого блока, и левый максимум, равный j+1 to i+k второго блока.

Answer 2

Просто переберите массив и сохраните k последние элементы в самобалансирующемся двоичном дереве .
Добавление элемента в такое дерево, удаление элемента и поиск текущего максимумастоит O(logk).

Большинство языков предоставляют стандартные реализации для таких деревьев.В STL, IIRC, это MultiSet.В Java вы должны использовать TreeMap (отображение, потому что вам нужно вести подсчет, сколько раз каждый элемент встречается, а Java не предоставляет мультиколлекции).

Псевдокод

for (int i = 0; i < n; ++i) {
    tree.add(a[i]);

    if (tree.size() > k) {
        tree.remove(a[i - k]);
    }

    if (tree.size() == k) {
        print(tree.max());
    }
}

Answer 3

Надеюсь, что это решение, которое вы ищете:

def MaxContigousSum(lst, n):
m = [0]
if lst[0] > 0:
    m[0] = lst[0]
maxsum = m[0]
for i in range(1, n):
    if m[i - 1] + lst[i] > 0:
        m.append(m[i - 1] + lst[i])
    else:
        m.append(0)
    if m[i] > maxsum:
        maxsum = m[i]
return maxsum

lst = [-2, 11, -4, 13, -5, 2, 1, -3, 4, -2, -1, -6, -9]
print MaxContigousSum(lst, len(lst))
**Output**
20 for [11, -4, 13]