My Java solution in O(n)

public class Solution {
public int maxArr(ArrayList A) {
if(A.size()==1)
{
return 0;
}
if(A.size()==0)
{
return 1;
}
// int max=1+(Math.abs(A.get(0)-A.get(1)));
// for(int i=0;i<A.size()-1;i++)
// {
// for(int j=i+1;j<A.size();j++)
// {
// int curr=Math.abs(A.get(i)-A.get(j))+Math.abs(j-i);
// max=Math.max(max,curr);
// }
// }

    int maxSums=A.get(0);
    int minSums=A.get(0);
    for(int i=0;i<A.size();i++)
    {
        maxSums=Math.max(maxSums,A.get(i)+i);
        minSums=Math.min(minSums,A.get(i)+i);
    }
    int sumsRes=maxSums-minSums;
    
    int maxDif=A.get(0);
    int minDif=A.get(0);
     for(int i=0;i<A.size();i++)
    {
        maxDif=Math.max(maxDif,A.get(i)-i);
        minDif=Math.min(minDif,A.get(i)-i);
    }
    int difsRes=maxDif-minDif;
    return Math.max(difsRes,sumsRes);
  
}

}

Click here to start solving coding interview questions