Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit.

Here is simple and easy approach using stack only.

#include <bits/stdc++.h>
using namespace std;

int main() {
	//code
	int t;
	cin>>t;
	while(t--)
	{
	    
	int n,x;
	cin>>n;
	vector<long int> v;
	
	for(int i=0;i<n;++i)
	{
	    cin>>x;
	    v.push_back(x);
	}
	

	
	stack< int> st;
	long  int mxar=0;
	long  int ar=0;
	 int i,j,l;
	for(i=0;i<n;)
	{
	    if(st.empty())
	    {
	        l=i;
	    st.push(i++);
	    }else if(v[i]>=v[st.top()])
	    st.push(i++);
	    else if(v[i]<v[st.top()])
	    {
	        
	          j=st.top();
	          st.pop();
	          
    	          if(st.empty())
    	          {
    	              ar=v[j]*(i);
    	              mxar=max(ar,mxar);
    	          }
    	          else
    	          {
    	              
    	              ar=v[j]*(i-st.top()-1);
    	              mxar=max(ar,mxar);
    	          }
	         }
	      
	    }
	    
	
	while(!st.empty())
	      {
	           j=st.top();
	          st.pop();
	          if(!st.empty())
	          {
	          ar=v[j]*(i-st.top()-1);
	          mxar=max(ar,mxar);
	          }
	      }
	      if(st.empty())
    	  {
	      ar=v[j]*(i);
	      mxar=max(ar,mxar);
    	  }
	
	cout<<mxar<<endl;
	
}
	return 0;
}