Dado un conjunto S de enteros positivos cuyos elementos no necesitan ser distintos, debo encontrar una suma mínima no negativa que no pueda obtenerse de ningún subconjunto del conjunto dado.

Ejemplo:if S = {1, 1, 3, 7}, podemos obtener0 como(S' = {}), 1 como(S' = {1}), 2 como(S' = {1, 1}), 3 como(S' = {3}), 4 como(S' = {1, 3}), 5 como(S' = {1, 1, 3}), pero no podemos conseguir6.

Ahora se nos da unaarray A, que consiste enN enteros positivos. Sus sonM consultas, cada una consiste en dos enterosLi yRi describa la consulta: necesitamos encontrar esta suma que no se pueda obtener de la matrizelements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]} .

Sé que lo encuentro por un enfoque de fuerza bruta que debe hacerse en O (2 ^ n). Pero dado1 ≤ N, M ≤ 100,000.Esto no se puede hacer. Así es su enfoque efectivo para hacerlo.