Pseudocode in Java

Given an array of non-negative integers, determine the area of the largest rectangle in the array. You can think of each value k in the array as a rectangle of width 1 unit and height k and then compute the largest area rectangle in the array where the largest area can span contiguous bars.

For example, if the array contains the values 1, 2, 3, 3, 2, 1 then the largest rectangle is area 8 and consists of the rectangle of height 2 from index 2 to index 5 (array indices start at 1).

(a) Design a brute force algorithm to compute the area of the largest rectangle in the array. Hint: You will not do better than O(n2).

(b) Design an incremental algorithm to compute the area of the largest rectangle in the array. Hint: You will need to use a stack to track the indices. Think about cases where you will need to backtrack.