Решение задачи №79 от UniLecs

max_rect.rs

type Bar = u32; //Тип столбцов гистограммы
type RectArea = u64; //Тип площади прямоугольников

fn max_rect(bar_chart: &[Bar]) -> RectArea {
    use std::collections::BTreeSet;
    use std::iter::FromIterator;
    
    //Собираем все высоты, присутствующие в гистограмме
    let heights = BTreeSet::from_iter(bar_chart.iter().cloned());

    //Для всех высот в гистограмме
    heights.into_iter().fold(0, |max_rect, height| {
        //Находим максимальное число идущих подряд столбцов
        //высотой не меньше текущей
        let max_length = bar_chart
            .iter().cloned()
            .fold((0, 0), |(max, len), x| {
                if x >= height {
                    let len = len + 1;
                    (max.max(len), len)
                } else {
                    (max, 0)
                }
            })
            .0;
        
        //и находим максимальное произведение числа идущих
        //подряд столбцов на текущую высоту (т. е. макcимальную
        //площадь прямоугольника, ограниченного гистограммой)
        max_rect.max(max_length * RectArea::from(height))
    })
}

//-------------------------------------------------------------

//Тесты
#[test]
fn do_tests() {
    let chart = [2, 1, 4, 5, 1, 3, 3];
    assert_eq!(max_rect(&chart), 8);

    let chart = [4, 3, 6, 4, 1, 2, 3, 4, 3, 4, 3, 2, 5, 3, 2];
    assert_eq!(max_rect(&chart), 20);

    let chart = [1, 2, 3, 4, 5, 6, 7, 8];
    assert_eq!(max_rect(&chart), 20);
}

//Проверяем, что случай пустой гистограммы обрабатывается корректно
#[test]
fn empty() {
    let chart = [];
    assert_eq!(max_rect(&chart), 0);
}

//Проверяем, что вычисления с максимальным для Bar значением
//не приведут к переполнению.
#[test]
fn no_overflow() {
    let max_bar = Bar::max_value();
    let chart = [max_bar, max_bar];
    assert_eq!(max_rect(&chart), 2 * RectArea::from(max_bar));
}

//Проверяем, что максимально возможная площадь прямоугольника
//умещается в RectArea. Предполагается, что
//usize::max_value() <= Bar::max_value()
#[test]
fn correct_types() {
    fn square(a: RectArea) -> RectArea {
        a * a
    }
    assert!(square(RectArea::from(u32::max_value())) <= RectArea::max_value());
}

Playground: https://play.rust-lang.org/?gist=d16bf4997992853dcc57f80bb1ab7528&version=stable