Bear and Blocks

DBlocks.java

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class DBlocks {

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

        int N = scanner.nextInt();
        int[] height = new int[N];
        int[] deadWhen = new int[N];

        for (int i = 0; i < N; i++) {
            height[i] = scanner.nextInt();
            // by default, al sides get destroyed.
            deadWhen[i] = Math.min(i + 1, N - i);
        }

        // check if anyone can die earlier
        for (int i = 0; i < N; i++) {
            if (height[i] < deadWhen[i]) {
                // this guy is dying early.
                deadWhen[i] = height[i];

                // update both sides accordingly
                int left = i - 1;
                int right = i + 1;
                int leftEffect = deadWhen[i] + 1;
                while (0 <= left) {
                    if (leftEffect < deadWhen[left]) {
                        deadWhen[left] = leftEffect;
                        leftEffect++;
                        left--;
                    } else {
                        break; // no more cascading effect
                    }
                }
                int rightEffect = deadWhen[i] + 1;
                while (right < N) {
                    if (rightEffect < deadWhen[right]) {
                        deadWhen[right] = rightEffect;
                        rightEffect++;
                        right++;
                    } else {
                        break;
                    }
                }
            }
        }

        int res = deadWhen[0];
        for (int i = 1; i < N; i++)
            res = Math.max(res, deadWhen[i]);
        writer.println(res);
        writer.flush();
    }
}