Find the maximum value of | Ai - Aj | + | i - j |: hackerearth.com practice problem Can you solve it?:


  Given an array 'A' consisting of 'n' integers, find the maximum value of the following expression:
  \$\lvert A_i - A_j\rvert + \lvert i - j\rvert\$


where \$A_i\$ is the element of the array at the i-th position (0-indexed array)

My solution:

def solve(n,l):
    ans=0
    for i in range(n):
        for j in range(n):
            if ans &lt; (abs(l[i]-l[j])+abs(i-j)):
                ans=(abs(l[i]-l[j])+abs(i-j))
                print(ans)


t=int(input())
for _ in range(t):
    n=int(input())
    l = list(map(int,input().split()))
solve(n,l)    


This code passes all the sample test cases but when I finally submit the code
for two inputs it shows wrong and
for all the other inputs it shows time limit exceeded.

Kindly point out what is wrong and what can be done in order to get the correct output.
The minor problem is that you are printing the result in the wrong place.

The major problem is that n may be up to 100,000.  This means you need to run 10,000,000,000 of your inner test.  And you may have only 0.02 seconds to do that.

The trick to dealing with that is probably to determine the maximum possible score of a given i and l[i], and skip the inner loop if it isn't worth it.  As part of this, you might find it beneficial to determine the range of the l[] values.

As an example, if you determine that all l[i]&lt;=5, then it isn't worth looking at i&gt;6 and i&lt;n-6 (or thereabouts... I'm not positive about the border condition).