Container With Most Water

Given n non-negative integers a1a2, …, an, where each represents a point at coordinate (iai). n vertical lines are drawn such that the two endpoints of line i is at (iai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

C++:
01 int maxArea(vector<int> &height) {
02     int n=height.size();
03     int* A=new int[n];
04     for(int i=0;i<n;i++)
05         A[i]=0;
06     for(int i=0,j=n1;i<; ){
07         if(height[i]<=height[j]){
08             A[i]=(ji)*height[i];
09             do{i++;}while((i<j)&&(height[i]<=height[i1]));
10         }else{
11             A[j]=(ji)*height[j];
12             do{j;}while((i<j)&&(height[j]<=height[j+1]));
13         }
14     }
15     int max=A[0];
16     for(int i=1;i<n;i++){
17         if(max<A[i])
18             max=A[i];
19     }
20     return max;
21 }
Advertisements
This entry was posted in Array and linked list, Greedy algorithm. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s