[go: up one dir, main page]
Scribd
Upload
14 views1 page

Largest Rectangle in Histogram in Stacks and Queues

The document describes a problem to find the area of the largest rectangle in a histogram represented by an array of heights. It outlines the input format, including the number of test cases and the constraints on the array size and values. The output should be the area of the largest rectangle for each test case, with specific sample inputs and outputs provided.

Uploaded by

Asif Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views1 page

Largest Rectangle in Histogram in Stacks and Queues

The document describes a problem to find the area of the largest rectangle in a histogram represented by an array of heights. It outlines the input format, including the number of test cases and the constraints on the array size and values. The output should be the area of the largest rectangle for each test case, with specific sample inputs and outputs provided.

Uploaded by

Asif Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

1/26/25, 4:14 PM Largest Rectangle in Histogram in Stacks and Queues

Largest Rectangle in Histogram


You are given an array A1 , A2 , … , AN of length N . A represents a
​ ​ ​

histogram which mean the height of the ith bar will be Ai units and the width
​

of each bar is 1 unit.

Find the area of the largest rectangle in the histogram.

Input Format
The first line of input will contain a single integer T , denoting the number
of test cases.
The first line of each test case contains an integer N - the length of the
array A.
The second line of each test case contains N space-separated integers
A1 , A2 , … , AN .
​ ​ ​

Output Format
For each test case, output on a new line the area of the largest rectangle in
the histogram.

Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 105
1 ≤ Ai ≤ 109
​

The sum of N over all test cases won't exceed 2 ⋅ 105 .

Subtasks
Subtask 1 (30 points): 1 ≤ N ≤ 1000
Subtask 2 (70 points): No further constraints.

Sample 1:

Input Output
3 12
4 15
https://www.codechef.com/learn/course/stacks-and-queues/LSTACKS02/problems/PREP22 1/1

You might also like