ДП. Оптимизация и не правильный вывод ответа

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

def calculate_max_team_size(skill_levels):
    skill_count = len(skill_levels)
    team_sizes = []

    for index in range(0, skill_count):
        dp = [0] * skill_count
        dp[index] = skill_levels[index]
        for sub_index in range(index + 1, skill_count):
            if skill_levels[sub_index] <= max(dp[:sub_index]):
                dp[sub_index] = skill_levels[sub_index]
        team_sizes.append(len(dp) - dp.count(0))

    return max(team_sizes)


def main():
    test_cases = int(input())
    for _ in range(test_cases):
        candidate_count = int(input())
        skill_levels = list(map(int, input().split()))
        results = calculate_max_team_size(skill_levels)
        print(results)


main()

Не проходит по некоторым тестам Второй код:

def max_team_size_1(skills):
    n = len(skills)
    dp_1 = []

    for i in range(0, n):
        dp = [0] * n
        dp[i] = skills[i]  # Инициализация dp с текущим навыком

        # Проверка, есть ли уже предыдущие элементы в dp_1
        if len(dp_1) > 0:
            # Если текущий навык больше максимального из предыдущих
            if skills[i] > max(skills[:i]):
                for j in range(i + 1, n):
                    # Проверка, может ли следующий кандидат быть добавлен
                    if skills[j] <= max(dp[:j]):
                        dp[j] = skills[j]
                dp_1.append(len(dp) - dp.count(0))  # Подсчет размера команды
                print(dp)  # Для отладки
            else:
                continue  # Если текущий навык не подходит, переходим к следующему i
        else:
            # Если dp_1 пуст, просто добавляем текущий навык
            for j in range(i + 1, n):
                if skills[j] <= max(dp[:j]):
                    dp[j] = skills[j]
            dp_1.append(len(dp) - dp.count(0))  # Подсчет размера команды
            print(dp)  # Для отладки

    return max(dp_1)  # Возвращаем максимальный размер команды


def main_1():
    t = int(input())
    for _ in range(t):
        n = int(input())
        if n == 1:
            print(1)  # Если только один кандидат, команда из одного
        else:
            skills = list(map(int, input().split()))
            results = max_team_size_1(skills)
            print(results)


main_1()

Параметр skills:Это список, содержащий уровни навыков сотрудников.

Переменные: n: количество сотрудников (длина списка skills). dp_1: список, который будет хранить размеры команд для каждого кандидата.

Внешний цикл: Проходит по каждому кандидату (индекс i от 0 до n - 1). Создает массив dp, который будет хранить уровень навыков, которые могут быть включены в команду, начиная с текущего кандидата.

Инициализация dp: dp[i] = skills[i]: устанавливает уровень навыка текущего кандидата в массиве dp.

Проверка на наличие предыдущих элементов в dp_1: Если dp_1 не пуст, проверяется, больше ли текущий уровень навыка skills[i] максимального уровня навыка среди всех предыдущих кандидатов (max(skills[:i])). Если да, то продолжаем добавлять кандидатов в dp.

Внутренний цикл: Проходит по всем последующим кандидатам (от i + 1 до n - 1).Проверяет, может ли текущий кандидат быть добавлен в команду, сравнивая его уровень навыка с максимальным уровнем среди всех уже добавленных кандидатов в dp. Если условие выполняется, добавляет уровень навыка в dp.

Подсчет размера команды:len(dp) - dp.count(0): вычисляет размер команды, вычитая количество нулей в dp (поскольку нули обозначают, что кандидат не был включен в команду).

Добавление размера команды: Добавляет полученный размер команды в список dp_1.

Возврат результата: Возвращает максимальный размер команды из всех возможных, который был сохранен в dp_1.