Оптимизация решения задачи python

Представляю Вам одно из возможных решений по оптимизации Вашего алгоритма:

import numpy as np
import time

row = np.array(input().split())
heights = np.array(input().split())
result = np.zeros(len(heights), dtype=int)

def right_sum(array, index, height):
    return len(array[index:][array[index:] != height])

def left_sum(array, index, height):
    return len(array[:index][array[:index] == height])

for i, height in enumerate(heights):
    maxCount = 0
    for j in range(len(row)):
        current = left_sum(row, j, height) * right_sum(row, j, height)
        if current > maxCount:
            maxCount = current
    result[i] = maxCount

print(' '.join(result.astype(str)))

Предложенный оптимизированный код использует библиотеку NumPy для создания массивов, которые работают быстрее и используют меньше памяти, чем обычные списки в Python.

Было использовано булевую индексацию, чтобы найти элементы, которые не равны или равны определенному значению. Позже использовалась функция len() для подсчета количества таких элементов.

Далее были задействованы генераторы списков для оптимизации кода. Вместо того, чтобы создавать отдельный список для результата, формируется массив нулей, который в последствии заполняется значениями, используя цикл и функцию enumerate(), которая позволяет перебирать значения массива вместе с их индексами.

Также была изменена логика цикла. Вместо того, чтобы проходить по каждому элементу списка row для каждого элемента списка heights, мы проходим по каждому элементу списка row только один раз и вычисляем максимальное значение для каждого элемента списка heights.

Метод astype() добавлен для преобразования элементов массива в строковые значения.

Так же провел небольшой эксперимент с одинаковыми входящими данными. По его результат, выполнение алгоритма удалось ускорить более чем в 3 раза.

Результат Вашего алгоритма:

Результат оптимизированого алгоритма:

По просьбе автора доработал алгоритм, без использования Numpy. Вышло с минимальным, но действенным вмешательством в оригинальный алгоритм. Этот код использует словарь heights_dict для сохранения значений maxCount для каждой высоты, поэтому выполнение кода становится быстрее. Как результат новый оптимизированный алгоритм исполняется более чем в 135 раз быстрее, чем исходный. И в 38 раз быстрее, чем первый вариант оптимизации.

Новый адаптированный алгоритм без использования NumPy:

import time

row = input().split(' ')
heights = input().split(' ')
result = []

def right_sum(array, index, height):
    rsum = 0
    for i in range(index, len(array)):
        if array[i] != height:
            rsum += 1
    return rsum

def left_sum(array, index, height):
    lsum = 0
    for i in range(0, index):
        if array[i] == height:
            lsum += 1
    return lsum

heights_dict = {}
for height in heights:
    if height in heights_dict:
        result.append(str(heights_dict[height]))
    else:
        maxCount = 0
        for i in range(0, len(row)):
            current = left_sum(row, i, height) * right_sum(row, i, height)
            if current > maxCount:
                maxCount = current
        heights_dict[height] = maxCount
        result.append(str(maxCount))

print(' '.join(result))

Результат оптимизированого алгоритма без NumPy:

Есть еще один вариант, это последняя модификация, где убраны повторяющиеся вычисления длин с помощью методов массива array[index:] и array[:index], которые позволяют находить подмассивы с помощью срезов и тем самым еще больше ускоряют выполнение данного кода.

Код последней модификации с срезами подмассивов:

import time

row = input().split(' ')
heights = input().split(' ')
result = []

def right_sum(array, index, height):
    rsum = 0
    for h in array[index:]:
        if h != height:
            rsum += 1
    return rsum

def left_sum(array, index, height):
    lsum = 0
    for h in array[:index]:
        if h == height:
            lsum += 1
    return lsum

heights_dict = {}
for height in heights:
    if height in heights_dict:
        result.append(str(heights_dict[height]))
    else:
        maxCount = 0
        for i in range(0, len(row)):
            current = left_sum(row, i, height) * right_sum(row, i, height)
            if current > maxCount:
                maxCount = current
        heights_dict[height] = maxCount
        result.append(str(maxCount))

print(' '.join(result))

Результат последней модификации с срезами подмассивов: