Maximum Non-overlapping Rectangles in a Histogram

You are given a histogram consisting of N contiguous rectangles with their bases parallel to the ground. Each rectangle has a width of 1, and the height of the i-th rectangle (from left to right) is an integer \(H_{i}\).

In this histogram, we want to choose at most \(K\) rectangles. Each chosen rectangle must have its base parallel to the ground and all sides of integer length. Moreover, aside from possibly touching at vertices or along edges, the interiors of the selected rectangles must not overlap. The objective is to maximize the sum of the areas of these rectangles. Let \(f(K)\) be the maximum total area achievable under these constraints.

Your task is to compute \(f(1)\), \(f(2)\), and \(f(3)\).

You need to implement the following function:

vector<long long> max_area(vector<int> H);

Here, the integer array \(H\) of size \(N\) represents the histogram such that the i-th element (0-indexed) corresponds to \(H_{i+1}\). The function should return an array of exactly 3 elements where the i-th element is \(f(i+1)\). Please note that the size of the returned array is important for scoring.

Note: Your submitted code should not contain any input/output operations.

inputFormat

An integer array H representing the histogram’s bar heights, where each bar has a width of 1. The i-th element of H corresponds to \(H_{i+1}\). There is no standard input, as your function max_area will be called directly.

outputFormat

An array of 3 integers: the first element is \(f(1)\), the second is \(f(2)\), and the third is \(f(3)\). Each \(f(K)\) represents the maximum total area that can be obtained by selecting at most \(K\) non-overlapping rectangles inside the histogram under the constraints described above.

sample

[2,1,5,6,2,3]

[10,14,16]