public class MaxSumLevel {
    public static int maxLevel(int[] A) {
        if(A == null || A.length == 0) return 0;

        Queue<Integer> queue = new LinkedList<>();
        int resLevel = 1;
        int curLevel = 1;
        int maxSum = A[0];
        queue.offer(0);
        while(!queue.isEmpty()) {
            int sum = 0;
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                int curIndex = queue.poll();
                sum += A[curIndex];
                if(curIndex * 2 + 1 < A.length) queue.offer(curIndex * 2 + 1);
                if(curIndex * 2 + 2 < A.length) queue.offer(curIndex * 2 + 2);
            }
            if(sum > maxSum) {
                maxSum = sum;
                resLevel = curLevel;
            }
            curLevel++;
        }
        return resLevel;
    }
}