Pregunta: dada una array que tiene 2n elementos, puede elegir n elementos de cualquier extremo de la array de modo que los valores obtenidos resulten en la suma máxima.
Ejemplos:
Input : 1 3 100 25 20 4 Output : 103
Enfoque: Inicialmente, probé el enfoque recursivo al mostrar ambas posibilidades de un elemento que puede incluirse o excluirse, pero me dijo que lo optimizara y se me ocurrió el enfoque de suma de prefijos.
Idea: La idea principal detrás del enfoque de suma de prefijos era que si seleccionamos elementos ‘x’ de la izquierda, podemos seleccionar elementos ‘n-x’ de la derecha.
int function(int arr[])
{
Int n = arr.size();
Int lpref[n], rpref[n]; // for left and right prefix sum
Lpref[0] = arr[0], rpref[n - 1] = arr[n - 1];
For(int i = 1; i < n; i++)
{
Lpref[i] = Lpref[i - 1] + arr[i];
}
For(int i = n - 2; i >= 0; i--)
{
rpref[i] = rpref[i + 1] + arr[i];
}
Int maxm = INT_MIN, m = n / 2;
For(int i = 0; i < m - 1; i++)
{
maxm =max(maxm, lpref[i]+rpref[n-1-i];
}
maxm = max(maxm, lpref[m - 1]);
maxm = max(maxm, rpref[n - m]);
return maxm;
}