给定一组正整数,其元素不需要是不同的,我需要找到不能从给定集合的任何子集获得的最小非负和.
例如:if S = {1, 1, 3, 7},我们可以得到0as (S' = {}),1as (S' = {1}),2as (S' = {1, 1}),3as (S' = {3}),4as (S' = {1, 3}),5as (S' = {1, 1, 3}),但是我们无法得到6.
现在我们给出一个array A由N正整数组成的.它们是M查询,每个查询由两个整数组成,Li并Ri描述我的查询:我们需要找到这个不能从数组中获得的Sum elements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]}.
我知道通过蛮力方法在O(2 ^ n)中完成它.但是给了1 ? N, M ? 100,000 …
algorithm ×1