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

code in C++11/C++14 (no pre-C++11!)

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