C++ code requirement

Problem One: Skylines A skyline is a geometric figure consisting of a number of variable-height boxes of width 1 placed next to one another that all share the same baseline. Here's some example skylines, which might give you a better sense of where the name comes from: HT .. 4 2 3 12 7 1 8305 4 3 2 1 1 3 7 4 2 Notice that a skyline can contain boxes of height 0. However, skylines can't contain boxes of negative height You're interested in finding the area of the largest axis-aligned rectangle that fits into a given skyline. For example, here are the largest rectangles you can fit into the above skylines: 5 8 6 9 6 4 2 3 1 2_1_1_8_;_0 4 3 2 1 1 3 7 4 2 Design an O(n)-time algorithm for this problem, where n is the number of constituent rectangles in the skyline. For simplicity, you can assume that no two boxes in the skyline have the same height. Follow the advice from my Assignment Policies handout when writing up your solution - give a brief overview of how your algorithm works. describe it as clearly as possible, formally prove correctness, and then argue why the runtime is O(n)