CareerCup

int main()
{
	ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
	int  t;
	cin>>t;
	while(t--)
	{
	int n;
	cin>>n;
	ll a[500005];
	for(int i=1;i<=n;i++)cin>>a[i];
		int l=1,r=n;
	ll ans=min(a[l],a[r])*(r-l);
	while(l<r)
	{
		ans=max(ans,min(a[l],a[r])*(r-l));
		if(a[l]<=a[r])l++;
		else r--;
	}
	cout<<ans<<endl;
}
}

Complexity - O(n)

import java.lang.*;
import java.util.*;

public class removeallbarsbuttwo{

	public static int getmax(int[] arr){
		int n = arr.length;
		int[][] dp = new int[n][n];
		
		for(int i=0; i < n; i++){
			dp[i][i] = 0;
		}
		
		dp[0][1] = 0;
		
		for(int i=1;  i < n-1; i++){
			dp[i][i+1] = 0;
		}
		
		int max = 0;
		
		for(int i=0; i < n-2; i++){
			for(int j=i+2; j < n; j++){
				dp[i][j] = Math.max(dp[i][j-1], (Math.min(arr[i], arr[j]) * (j - i -1)));
				if(dp[i][j] > max){
					max = dp[i][j];
				}		
			}
		}
		
		return max;
	}

	public static void main(String[] args){
		int[] arr = {10, 5, 6, 12, 14};
		System.out.println(getmax(arr));
	}
}

import java.lang.*;
import java.util.*;

public class removeallbarsbuttwo{

	public static int getmax(int[] arr){
		int n = arr.length;
		int[][] dp = new int[n][n];
		
		for(int i=0; i < n; i++){
			dp[i][i] = 0;
		}
		
		dp[0][1] = 0;
		
		for(int i=1;  i < n-1; i++){
			dp[i][i+1] = 0;
		}
		
		int max = 0;
		
		for(int i=0; i < n-2; i++){
			for(int j=i+2; j < n; j++){
				dp[i][j] = Math.max(dp[i][j-1], (Math.min(arr[i], arr[j]) * (j - i -1)));
				if(dp[i][j] > max){
					max = dp[i][j];
				}		
			}
		}
		
		return max;
	}

	public static void main(String[] args){
		int[] arr = {10, 5, 6, 12, 14};
		System.out.println(getmax(arr));
	}
}

public int getMaxVolume(int[] heights){
		
		int max = 0;
		for(int i=0;i<heights.length-1;i++){
			for(int j=i+2;j<heights.length;j++){
				int w = j-i-1; 
				int l = Math.min(heights[i], heights[j]);
				max= Math.max(max, w*l);
				
			}
		}
		
		return max;
	}

- Create a array of bars sorted by height (e.g., Y coordinate).
- Use a 'sweep-line' going from the top-most bar down to '0' from bar to bar in the array maintaining 'leftmost' and 'rightmost' intersected bars and max volume.

O(sort time) + O(n).
Sorting can be done in O(N) for integers using radix sort.

int result(Vector<int> vec){
int max=0;
for(int i=0;i<vec.size()-2;i++){
if(vec.get(i)*(vec.size()-2-i)>max)max=vec.get(i)*(vec.size()-2-i);
}
return max;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#define MAX 100005
using namespace std;

int Height[MAX];


bool cmp(const pair<int,int> &a,const pair<int,int> &b){
    return (a.first<=b.first);
}

int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>Height[i];
    }
    vector<pair<int,int> > L,R;
    R.push_back(make_pair(Height[n-1],n-1));
    for(int i=n-2;i>=0;i--){
        vector<pair<int,int> >::iterator low=lower_bound(R.begin(),R.end(),make_pair(Height[i],-1),cmp);
        if(low!=R.end()){
            ans=max(ans,((*low).second-i-1)*Height[i]);
        }
        if(Height[i]>((R.back())).first){
            R.push_back(make_pair(Height[i],i));
        }
    }
    
    L.push_back(make_pair(Height[0],0));
    for(int i=1;i<n;i++){
        vector<pair<int,int> >::iterator low=lower_bound(L.begin(),L.end(),make_pair(Height[i],-1),cmp);
        if(low!=L.end()){
            ans=max(ans,(i-(*low).second-1)*Height[i]);
        }
        if(Height[i]>((L.back())).first){
            L.push_back(make_pair(Height[i],i));
        }
    }
    cout<<ans<<endl;
    return 0;
}

Complexity : O(n*logn)

package Practice;

public class MaxCapacitybwBar {

/**
* @param args
*/
public static int getmax(int[] arr){
int n = arr.length;

int maxvalue =0;
int curvalue = 0;
for (int i=0;i<n-2;i++)
for(int j=i+2;j<n;j++)
{
curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
//System.out.println("curvalue"+curvalue);
if(curvalue>maxvalue)
maxvalue=curvalue;

}

return maxvalue;
}

public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}

}

package Practice;

public class MaxCapacitybwBar {

	/**
	 * @param args
	 */
	public static int getmax(int[] arr){
		int n = arr.length;
	
		int maxvalue =0;
		int curvalue = 0;
		for (int i=0;i<n-2;i++)
			for(int j=i+2;j<n;j++)
			{
				curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
				System.out.println("curvalue"+curvalue);
				if(curvalue>maxvalue)
					maxvalue=curvalue;
					
			}
		
		return maxvalue;
	}

	public static void main(String[] args){
		int[] arr = {10, 5, 6, 12, 14};
		System.out.println(getmax(arr));
	}

}

package Practice;

public class MaxCapacitybwBar {

/**
* @param args
*/
public static int getmax(int[] arr){
int n = arr.length;

int maxvalue =0;
int curvalue = 0;
for (int i=0;i<n-2;i++)
for(int j=i+2;j<n;j++)
{
curvalue =Math.max(maxvalue ,(Math.min(arr[i],arr[j]) *(j-i-1)));
System.out.println("curvalue"+curvalue);
if(curvalue>maxvalue)
maxvalue=curvalue;

}

return maxvalue;
}

public static void main(String[] args){
int[] arr = {10, 5, 6, 12, 14};
System.out.println(getmax(arr));
}

}