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