La altura de la cima de una montaña X33007
Hay que implementar una función que recibe un vector v de naturales que tiene dos partes, una primera parte estrictamente creciente y una segunda parte estrictamente decreciente. En otras palabras, existe un índice i válido del vector tal que, para todo j anterior a i se cumple v[j] < v[j+1], y para todo j posterior a i se cumple v[j−1] > v[j]. Se garantiza que el vector tiene como mínimo tres elementos y que su valor máximo (es decir, v[i], para el i mencionado) no se encuentra ni exactamente al principio ni al final.
La función deberá retornar el valor máximo de v. Esta es la cabecera:
// 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);
Observación Sólo tenéis que enviar el procedimiento requerido; el programa principal será ignorado.
Observación
Evaluación sobre 10 puntos:
- Solución lenta: 5 puntos.
- Solución rápida: 10 puntos.
Entendemos como solución rápida aquella que es correcta, de coste logarítmico y capaz de superar los juegos de prueba públicos y privados. Entendemos como solución lenta aquella que no es rápida, pero es correcta y capaz de superar los juegos de prueba públicos.
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