Максимальная сумма увеличения подпоследовательности

Question

Итак, я создал простой код python с использованием программирования Dynami c, чтобы решить проблему максимальной возрастающей подпоследовательности. Вопрос в следующем:

Задан массив массива из N натуральных чисел. Найти сумму подпоследовательности увеличения максимальной суммы данного массива.

Ввод: Первая строка ввода содержит целое число T, обозначающее количество тестовых случаев. Первая строка каждого теста - это N (размер массива). Вторая строка каждого теста содержит элементы массива.

Вывод: Для каждого теста выведите требуемый ответ в новой строке.

В моем решении я вычисляю максимальную сумму в списке под названием 'суммы'

#code
T = int(input())
for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    sums = list(arr)
    max_sum = arr[0]

    for j in range(1,N):
        for i in range(0,j):
            if arr[i]<arr[j] and sums[j]<sums[i]+arr[j]:
                sums[j] = (sums[i]+arr[j])
                if sums[j]>max_sum:
                    max_sum = sums[j]

    print(max_sum)

Мой вывод: Ваша программа заняла больше времени чем ожидалось. Превышен лимит времени. Ожидаемый лимит времени <2,32 сек. Подсказка: пожалуйста, оптимизируйте свой код и повторите отправку. </em>

Как мне еще оптимизировать этот код?

Answer 1

Я думаю, что это будет работать

def max_inc(a):
    max = a[0]
    prev = a[0]
    current = a[0]
    for i in range(1,len(a)):
        if a[i]>prev:
            current+=a[i]
            if current>max:
                max = current
        else:
            current = 0
        prev = a[i]
    return max

в O (n)