most-water.cpp (1114B)
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 6 //Leet Ratings 7 // Speed Memory 8 //Total 1475ms 59.1MB 9 //Beats 5.2% 8.27% 10 //This is the brute force method which I will optimize 11 //by using an inverted iteration from the end and do checks 12 //like I have with the last height on the lower bound. 13 14 int return_size(int x1, int x2, int y1, int y2){ 15 if(y1 > y2){ 16 return ((x2-x1) * y2); 17 } 18 else{ 19 return ((x2-x1) * y1); 20 } 21 } 22 23 int maxArea(vector<int>& height) { 24 int largest_area = 0; 25 int last_height = -1; 26 for(int i = 0 ; i < height.size() ; ++i){ 27 if(height[i] > last_height){ 28 last_height = height[i]; 29 for(int x = i ; x < height.size() ; ++x){ 30 int curr_val = return_size(i , x, height[i], height[x]); 31 if( curr_val > largest_area){ 32 largest_area = curr_val; 33 } 34 } 35 } 36 } 37 return largest_area; 38 } 39 40 41 42 int main(){ 43 44 vector<int> heights = {3, 1,2, 4, 5, 6, 7,8,8,8,8,4,4,4,4,4,4,4,4}; 45 cout << maxArea(heights) << endl; 46 return 0; 47 }