"DELISH" TLE is occuring

TLE is occuring, logic is correct, how can i optimize running time?

def right(l,start,last):
    temp1=l[start]
    temp2=l[start]
    for i in range(start+1,last+1):
        temp1=max(grid[start][i],temp1)
        temp2=min(grid[start][i],temp2)
    return [temp1,temp2]
def left(l,start,last):
    temp1=l[last]
    temp2=l[last]
    for i in range(start,last+1):
        temp1=max(grid[0][last]-grid[0][i]+l[i],temp1)
        temp2=min(grid[0][last]-grid[0][i]+l[i],temp2)
    return [temp1,temp2]
t=int(input())
for p in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    grid=[[None]*n for c in range(n)]
    for i in range(n):
        grid[i][i]=l[i]
    for i in range(n):
        for j in range(i+1,n):
            if i==j:
                grid[i][j]=l[i]
            else:
                grid[i][j]=grid[i][j-1]+l[j]
    final=[]
    for i in range(1,n):
        final.append(max(abs(right(l,i,n-1)[0]-left(l,0,i-1)[0]),abs(right(l,i,n-1)[0]-left(l,0,i-1)[1]),abs(right(l,i,n-1)[1]-left(l,0,i-1)[0]),abs(right(l,i,n-1)[1]-left(l,0,i-1)[1])))
    print(max(final))