c++ - 最大面积直方图 动态规划 C++

Question

我试图在直方图中获得最大面积。

我已经使用蛮力算法做到了，并且效果很好，但是我想使用动态编程来做到这一点。

我不需要任何代码，我只想知道编写它但使用动态编程的想法

这是我的蛮力代码。注意：建筑物的数量是直方图中的列数

int getMaxArea(build building[], int NumOfBuildings) {

    int BuildingHeight = 0; //Height of Smallest Building of current Iteration.
    int Total_BuildingLength = 0; // Total length of current buildings iteration
    int max_area = 0; // Maximum Area Calculated
    int CurrentArea; //Store Current Area

    int i = 0;
    while (i < NumOfBuildings)
    {
        int j = i;
        BuildingHeight = building[j].height;

        while (j < NumOfBuildings) //(J)Iterate to the the last building starting from each (i) building. 
        {
            if (BuildingHeight >= building[j].height){
                BuildingHeight = building[j].height; // At Every Iteration assign new Smallest height for area calculation

            }
            // Each Step calculates Area.
            Total_BuildingLength += building[j].length;
            CurrentArea = BuildingHeight * Total_BuildingLength;

            if (max_area < CurrentArea){
                max_area = CurrentArea;
            }

            j++;
        }
        //Reset Length
        Total_BuildingLength = 0;
        i++;
    }
    return max_area; 
}

标签： c++algorithmhistogramdynamic-programmingbrute-force