The height of a mountain's summit X33007
You must implement a function which receives a vector v 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 i in v such that, for all j before i the condition v[j] < v[j+1] is true, and for all j after i the condition v[j−1] > v[j] is true. It is guaranteed that the vector v has at least three elements, and that the maximum (i.e., v[i] for the i 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 v. 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