6549번: 히스토그램에서 가장 큰 직사각형

#include<cstdio>

#define csDown() {--cs; h = (h > n[cs]) ? n[cs] : h;}

#define ceUp() {++ce;h = (h > n[ce]) ? n[ce] : h;}

#define min(a,b) (a>b)?b:a

#define max(a,b) (a>b)?a:b

#define ll long long

int n[100001];

ll findMax(int s, int m, int e);

int main()

{

while (1)

{

scanf("%d", &n[0]);

if (n[0] == 0)

return 1;

for (int i = 1; i <= n[0]; ++i)

scanf("%d", &n[i]);

printf("%lld\n", findMax(1, ((1 + n[0]) / 2), n[0]));

}

}

ll findMax(int s, int m, int e)

{

int max, cs = m, ce = m + 1, h = min(n[cs], n[ce]);

if (s == e)

return n[s];

ll leftVal = findMax(s, ((s + m) / 2), m);

ll rightVal = findMax(m + 1, ((m + e + 1) / 2), e);

leftVal = max(leftVal, rightVal);

ll centerVal = 2 * h, temp;

while (cs >= s && ce <= e)

{

if (cs == s&&ce == e)

break;

else if (cs > s && ce < e)

if (n[cs - 1] > n[ce + 1])

{

csDown();

}

else

{

ceUp();

}

else if (cs > s)

{

csDown();

}

else if (ce < e)

{

ceUp();

}

temp = (ll)(ce - cs + 1)*(ll)h;

centerVal = max(centerVal, temp);

}

return max(leftVal, centerVal);

}