最大和递增子序列

Question

所以我用动态编程做了一个简单的python代码来解决最大递增子序列的问题。问题如下:

给定一个数组 arr 的 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)

我的输出：你的程序花费了比预期更多的时间。超出时间限制。预期时间限制

如何进一步优化此代码？

Answer 1

更多可读性：

def maxSumIncreasingSubsequence(array):

    sums = [num for num in array]
    maxSumIdx = 0

    for i in range(len(array)):
        currVal = array[i]
        for j in range(i):
            prevVal = array[j]
            if currVal > prevVal and sums[j] + currVal >= sums[i]:
                sums[i] = sums[j] + currVal
     
        if sums[i] >= sums[maxSumIdx]:
            maxSumIdx = i

    return sums[maxSumIdx] 

T = int(input())
for _ in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    maxSumIncreasingSubsequence([10, 70, 20, 30, 50, 11, 30])

Answer 2

我想这能行

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)中