The State of California is interested in creating ways to retain precious rain water so it doesn't drain to ground or to the Pac Blue completely. The Department wants to arrive at metrics to help determine the best way to preserve rain water. One metric calls for excavating soil out of the ground to create "pockets" or retention ponds that can hold the most amount of rain water. No terrain is flat so this task involves measuring elevation profile of the terrain. Generally a 2-D terrain can be represented by stakes (vertical bars) in the following graph:

In the above example the terrain profile in 2D can be represented by data inside an array of [0, 5, 3, 1, 2, 0, 4, 6, 9, 0, 0, 0]. Each square box is of 1x1 unit. The max amount of water retention occurs if we dig into ground 5 units deep at array index 1, and extend the space out to array index 8 forming a rectangle of 7x5 = 35 square units. Thus a retention pond of cross sectional area of 35 units is the max one we can create out of this elevation profile.

Another example:

The elevation profile for the above plot of land is [1, 2, 3, 1, 2, 1, 4, 8, 2, 2, 2, 0]. One can form the largest cross sectional area by excavating soil at array index 1 and extend that area all the way to array index 10 forming a rectangle of area 2x9 = 18 square units. Thus this is the largest retention pond cross sectional one can create from this terrain.

Remember the proposal calls for digging into the ground, not setting up above-ground containers which can be more costly. Your goal is to determine that cross sectional area of the future retention pond based on any terrain profile as input.

For this assignment write the following function that takes in a pointer reference to an array of any arbitrary elevation profile and its array size, and outputs the max cross sectional area of the biggest pond based on this profile:

int getMaxPond(int* arr, int size)

Examples:

input: [22,31,1,23]

output: 66

input: [1]

output: 0

input: [1,3,5]

output: 3

input: [3,2,1]

output: 2 (see below graphical illustration - either you take the orange box or red you end up with a max area of 2)

input: [1,1,1,1,1,1,1,1,1]

output: 8

input: [1,99,1]

output: 2

Constraints / Assumptions:

The terrain map is never NULL, namely arr.length is always > 0

X axis represents width (distance); the distance between two adjacent elevation (height) points is one unit

Y axis represents elevation (height) in the same unit as x-axis

The function returns 0 if there is not enough soil to create that cross sectional area (namely array containing just 1 unit width)

(UPDATED) Input array (arr) is passed in by pointer into the function

You should submit a fully working console program however your main() function isn't graded; only the above referenced function is

It is your responsibility to compile your code in C++11/C++14 (no pre-C++11!). Failure to do that means your code isn't compilable and you will receive 0 point

Wrong function signature receives -1 styling point

Logic: 9 points (-1 point for each test case failure; -1 for incorrect function signature)

Styling/Documentation: 1 point

Input: [0, 5, 3,1, 2, 0, 4, 6, 9, 0, 0, 0] Max Area -7x5 35 units Input: [0, 5, 3,1, 2, 0, 4, 6, 9, 0, 0, 0] Max Area -7x5 35 units