def max_sum_distance(arr):
    """
    Computes M = max{arr[i] + arr[j] + (j - i) | 0 <= i < j <= n}.

    Intuition:
        Maximizing the separable bivariate objective function is equivalent to
        maximizing two univariate objective functions: just rewrite!
            M = max{arr[i] - i} + max{arr[j] + j}
    """
    n = len(arr)
    diff_part = max(arr[i] - i for i in range(n))
    sum_part = max(arr[j] + j for j in range(n))
    return diff_part + sum_part