The height of a mountain's summit X33007
You must implement a function which receives a vector of natural numbers with two parts. In the first, elements have strictly increasing values, and in the second, they have strictly decreasing values. More formally, there is a valid index in such that, for all before the condition is true, and for all after the condition is true. It is guaranteed that the vector has at least three elements, and that the maximum (i.e., for the mentioned previously) does not occur exactly at the beginning or exactly at the end of the vector.
The function must return the maximum value of . This is the header:
// Pre: Let n be v.size(). Then n >= 3 and for all i in {0..n-1}, v[i] >= 0.
// Also, there exists i in {1..n-2} such that v[0..i] is strictly increasing and
// v[i..n-1] is strictly decreasing.
// Post: Returns the maximum value of v.
int summitOfMountain(const vector<int> &v);Observation
You only need to submit the required procedure; your main program will be ignored.
Observation
Evaluation over 10 points:
Slow solution: 5 points.
Fast solution: 10 points.
We define the fast solution to be one that is correct, of logarithmic cost and passes both the public and private test cases. We define a slow solution to be one that is not fast, but it is correct and passes the public test cases.
summitOfMountain([10, 11, 15, 7]) = 15 summitOfMountain([7, 12, 6, 3]) = 12 summitOfMountain([28, 65, 63, 59, 56, 51, 47, 44, 41, 36, 35, 32, 25, 24, 21, 16, 13, 9, 7]) = 65 summitOfMountain([9, 51, 46, 45, 42, 41, 36, 33, 29, 24, 22, 21, 19, 16, 11, 10, 7]) = 51 summitOfMountain([14, 17, 19, 21, 26, 31, 32, 33, 38, 42, 9]) = 42 summitOfMountain([6, 11, 21, 16]) = 21 summitOfMountain([2, 4, 5, 10, 16, 18, 21, 25, 27, 28, 34, 39, 53, 50, 48, 44, 30, 13]) = 53 summitOfMountain([5, 9, 11, 12, 16, 17, 27, 32, 37, 40, 42, 46, 48, 51, 52, 62, 59, 57, 22]) = 62 summitOfMountain([13, 21, 17, 9, 5]) = 21 summitOfMountain([10, 16, 13]) = 16 summitOfMountain([13, 26, 21, 20, 19, 14, 10, 5, 4]) = 26 summitOfMountain([18, 23, 29, 27, 14, 11, 9]) = 29 summitOfMountain([1, 5, 6, 7, 14, 16, 20, 24, 26, 33, 38, 44, 41, 29, 19, 9]) = 44 summitOfMountain([10, 12, 24, 28, 19, 17]) = 28 summitOfMountain([1, 2, 12, 9, 7]) = 12 summitOfMountain([11, 15, 23, 30, 31, 34, 37, 39, 45, 48, 50, 41, 28, 18, 8]) = 50 summitOfMountain([8, 13, 5]) = 13 summitOfMountain([6, 9, 10, 11, 3]) = 11 summitOfMountain([9, 15, 14, 8, 4]) = 15 summitOfMountain([5, 10, 20, 15]) = 20