20. Гистограмма и прямоугольник

Не решаласьСредняя

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.

Гистограмма

Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме.

Формат ввода

В первой строке входного файла записано число N (0<N1060 \lt N \le 10^6) — количество прямоугольников гистограммы. А затем следует N целых чисел h1,...,hnh_1, ..., h_n, где 0hi1090 \le h_i \le 10^9. Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1

Формат вывода

Выведите площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.

Ограничения

Ограничение времени

1 с

Ограничение памяти

256 МБ

Пример 1

Ввод
7 2 1 4 5 1 3 3
Вывод
8

Теги

Нужно войти, чтобы отправить решение.Войти
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
/*
Для чтения входных данных необходимо получить их
из стандартного потока ввода (stdin).
Данные во входном потоке соответствуют описанному
в условии формату. Обычно входные данные состоят
из нескольких строк.

Можно использовать несколько функций для чтения из stdin:
* scanf() -- читает данные из потока;
* fgets() -- читает строку из потока;
* gets() -- читает строку из потока до символа '\n'.

Чтобы прочитать из строки стандартного потока:
* число -- int var; scanf("%d", &var);
* строку -- char svar[100]; scanf("%s", svar);
* массив чисел известной длины --
int len; scanf("%d", &len);
int* arr = (int*) malloc(len * sizeof(int));
for (int i = 0; i < len; ++i)
scanf("%d", &arr[i]);
* последовательность слов до конца файла --
char word[100];
while (scanf("%s", word) == 1) {
// do something with word
}

Чтобы вывести результат в стандартный поток вывода (stdout),
можно использовать функцию printf().

Возможное решение задачи "Вычислите сумму A+B":


int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
*/

return 0;
}