The area of largest rectangle constained in a skyline --- Dynamic Programming

Use "efficient frontier" method.
Basic idea is for each i, go left and right to find the first index j whose value A[j] is smaller than A[i], then the rectangle contained in the skyline is covered by the left and right value.
Use stack to store the compare information. It has complexity O(N),


It is a classical DP problem start from the middle and go both ways.

Code:

int LargetRectangle(const vector &A)
{
   stack stk;
   vector L;

   for(int i=0; i   {
       while(!stk.empty() && A[stk.top()]>=A[i])  stk.pop();

       L.push_back( stk.empty() ? -1 : stk.top()  );

       stk.push(i);
   }

   while(!stk.empty())  stk.pop();

   vector R(A.size());
   for(int i=A.size()-1; i>=0; --i)
   {
       while (!stk.empty() && A[stk.top()] >= A[i]) stk.pop();
       R[i] = stk.empty() ? A.size():stk.top();
       stk.push(i);
   }

   int max_area =0;
   for(int i=0; i   {
       int temp  = A[i]*(R[i]-1-L[i]-1+1);
       max_area = temp > max_area ? temp : max_area;
   }
    return max_area;
}