python - 交替子序列 SPOJ Python (ALTSEQ)

Question

这是我第一次在像 SPOJ 这样的平台上尝试编码实践。我使用了自下而上的动态编程方法，并且我提交了以下解决方案，以找到 +ve 和 -ve 数字的交替子序列的最大长度。它是数组的最长递增子序列的程序变体。它显示超出时间限制。有人可以告诉我如何进一步优化以下程序吗？PS此解决方案在hackerEarth平台提交成功

def alternatingSeq(arr,n):
    if(n==1):
        return 1

    dp = [1 for i in range(n)]

    res = 0
    for i in range(1,n):

        for j in range(i):
            if( ((arr[i]<0 and arr[j] > 0 and -arr[i] > arr[j])
            or (arr[i]>0 and arr[j] < 0 and arr[i] > -arr[j])) 
            and dp[i] < 1 + dp[j]):
                dp[i] = 1 + dp[j]


        if(dp[i] > res):
            res = dp[i]

    return res

n = int(input())
arr = [int(i) for i in input().split()]
print(alternatingSeq(arr,n))