Алгоритм для подсчета максимальной последовательности в строке по заданному правилу

#алгоритм

Есть правило для подсчета максимальной последовательности из строки (строка состоит
из английский букв и цифр):

Выбирается n-ое количество границ внутри строки, таким образом чтобы перед каждым
было число. Далее длина строки внутри каждой из границ умножается на число перед ней.
И суммируется с остальными. Нужно определить какая максимальная строка может получится. 

Пример для наглядности:
Для строки '10j19k87d' максимальная длина получится равна 10*4+87*1=127.
Оптимальное расположение границ: 10[j19b]87[d]
Можно конечно расположить и таким образом: 10[j]19[b]87[d], но тогда длина будет
равна 10*1+19*1+87*1=116, что меньше предыдущей.

Пробовал решить перебором, не проходит по времени (ограничение 1 секунда, а максимальное
количество символов 10^5)

Подскажите подход, который позволит сократить время вычислений
    

Ответы

Ответ 1

Это типичная задача на динамическое программирование. Решил я её соответствующим образом:

def is_digit(c):
    return ord(c) >= ord('0') and ord(c) <= ord('9')

def is_num(s):
    for i in s:
        if not is_digit(i):
            return False

    return True

def get_next(a, idx):
    for i in range(idx + 1, len(a)):
        if a[i] > a[idx]:
            return i

    return -1

s = input()
if is_num(s):
    print(int(s[:-1]))
    exit(0)


nums = []
letters = []

temp = ''
flag = False
for c in s:
    if is_digit(c):
        temp += c
    else:
        if len(temp) > 0:
            nums.append(int(temp))
            temp = ''
            flag = False

        if flag:
            letters[-1] += 1
        else:
            letters.append(1)
            flag = True

#print(nums, letters)

l = len(letters)
dp = [0] * l
dp[0] = nums[0] * letters[0]
idx = 0
length = 0
nxt = -1
for i in range(1, l):
    if i < nxt:
        continue

    if nums[i] > nums[idx]:
        #idx = i
        nxt = get_next(nums, i)
        temp_len = 0
        if nxt == -1:
            nxt = len(nums)

        temp_len = sum(letters[i:nxt]) + sum([len(str(j)) for j in nums[i + 1: nxt]])
        #print(i, nxt, temp_len)

        first = nums[idx] * (letters[i] + len(str(nums[i])))
        second = nums[i] * temp_len

        if first > second:
            dp[i] = dp[i - 1] + first
        else:
            dp[i] = dp[i - 1] + second
            idx = i
    else:
        dp[i] = dp[i - 1] + nums[idx] * (letters[i] + len(str(nums[i])))

print(max(dp))


Как мне кажется, код говорит сам за себя: разобьём строку на блоки чисел и других
символов: nums, letters. dp[i] - ответ для блока с индексом i, очевидно, что dp[0]
будет равен первому числу умноженному на первую подстроку символов (других вариантов
просто нет), далее будем считать ответ для очередного блока перебрав 2 варианта:

Продолжить предыдущую серию, то есть 10b19b -> 10[b19b]
Начать новую серию, то есть 10b19b -> 10[b] + 19[b]

Жадно выбираем наиболее подходящий вариант и переходим к следующему блоку.

Примечание

Код написан с целью максимально быстрой работы программы, а также понятности для
новичков, поэтому не использовал слишком много встроенных функций и одно строчных выражений.

Кроме того, подразумевается, что входная строка будет иметь вид [число], [строка],
[число], [строка], иначе не понятно, как считать ответ для такой строки.

Edit

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