Array modification

M as a prisoner loves playing with his array $a_1,a_2,...,a_n$, he can do following operation as much as he wants:

• Choose two integers $i,j$ that $1\le i,j\le n$ and $|i-j|=1$ and also $a_i\ge 2$.
• Then add 1 to $a_j$ ($a_j=a_j+1$) and subtract 2 from $a_i$ ($a_i=a_i-2$).

M thinks beautifulness of an array is maximum value of it ($max(a_1,a_2,...,a_n)$).

What is the maximum value of beautifulness that M can get after doing above operation as much as he wants?

Example:

Input: n=5, arr[] = { 3, 2, 4, 1, 5 }
Output: 6

Approach

Java

public class ArrayModification {

    public static void main(String[] args) {

        int n = 5;
        long a[] = { 3, 2, 4, 1, 5 };
        long left[] = new long[n];
        long right[] = new long[n];
        long sum1 = 0, sum2 = 0;
        for (int i = 0; i < n; i++) {
            sum1 = (a[i] + sum1) / 2;
            left[i] = sum1;
            sum2 = (sum2 + a[n - i - 1]) / 2;
            right[n - i - 1] = sum2;
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            long val = a[i];
            if (i - 1 >= 0)
                val += left[i - 1];
            if (i + 1 < n)
                val += right[i + 1];
            ans = Math.max(ans, val);
        }
        System.out.println(ans);

    }

}