//Problema clásico de selección de actividades ponderadas

/* Ejemplo datos de entrada
Actividad:   0 1 2 3 4 5
-------------------------
T inicio     0 1 4 2 6 7
T fin        3 5 6 7 8 9
Beneficios   2 4 4 7 2 2

i    : 0  1  2  3  4  5
------------------------
p(i) :-1 -1  0 -1  2  3

*/
// p[] es un array del mismo tamaño que beneficios pero que indica
// la actividad compatible mas cercana con tiempo de fin menor.
private static int sel(int i)
{
        if (i==-1)
                return 0;
        else
                return Math.max( sel(i-1) , beneficios[i]+sel(p[i]) );
}

// Primera aproximación incorrecta en iterativo.
private static int sel(int i)
{
    int a, b = 0, resa, resb = 0;

    if (i == -1)
    {
        return 0;
    }
    else
    {
        // sel(i-1)
        for (int a = i - 1; a >= 0; a--)
        {
            resa = Math.max(resa, beneficios[i] + p[a]);
        }

        // sel(p[i])
        for (int b = i; b >= 0; b--)
        {
            resb = Math.max(resb, beneficios[i] + p[b]);
        }

        return Math.max(resa , beneficios[i] + resb)
    }
}