1

Say we have an array with some numbers in it, and we are given a value d (where d >= 1) that dictates a certain required index. How would we find the largest sum of values bounded by d. Here is an example:

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 3

Would return 4000 + 5000 = 9000 (since there is at least a distance of 3 between these two numbers). But in this case:

arr = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

Would return 4000 + 2500 + 5000 = 11500.

edit: More explanation - We need to find the largest possible sum in an array. The only trick is that we cannot include numbers that are less than d index away. In the second example we could easily just sum all the numbers to get the largest value, but since we are bounded by d = 2, we have to pick a combination where numbers are not < distance 2 away. Another example might include 3000 + 2500 + 5000 = 10500. If you look at my second solution 11500 > 10500, therefore this is not the optimal answer

augurar
  • 12,081
  • 6
  • 50
  • 65
  • Can you please explain the 2nd case? – ksohan Apr 18 '21 at 00:27
  • I’m thinking the language needs to be tightened up. As given, it could be interpreted in different ways. I don’t know, for example, what “bounded by d” means. – Howlium Apr 18 '21 at 00:32
  • I believe the idea is to find a maximum-sum subsequence `[A[i1], A[i2], ...]` such that the difference between each index is at least `d`. – augurar Apr 18 '21 at 00:46
  • your question needs more clarification – zoldxk Apr 18 '21 at 00:47

2 Answers2

1

This problem can be efficiently solved using a dynamic programming approach.

Let A be the input array and d be the gap size. Then for you can construct an array B such that B[i] is the maximum sum for the first i+1 elements of A. You can compute the elements of B by a simple recurrence, and the last element contains the solution:

def solve(A, d):
    n = len(A)
    B = [0] * n
    B[0] = A[0]
    for i in range(1, d):
        B[i] = max(A[i], B[i-1])
    for i in range(d, n):
        B[i] = max(A[i] + B[i-d], B[i-1])
    return B[-1]
augurar
  • 12,081
  • 6
  • 50
  • 65
0

You can do it in a single pass by iteratively computing the best sum for each prefix.

Once you have the best sum for each prefix up to but not including i, for i the best sum will either not include element i (and thus be equal to prefix_sums[i - 1]), or include element i, and thus be equal to i + prefix_sums[i - d] (get element i, and the best sum of elements that are at least d away from i-th element).

a = [3000, 4000, 2000, 2500, 3500, 5000]
d = 2

prefix_sums = [a[0]]
for x in a[1:]:
    cur = x if len(prefix_sums) < d else x + prefix_sums[-d]
    cur = max(cur, prefix_sums[-1])
    prefix_sums.append(cur)

print(max(prefix_sums))
Ishamael
  • 12,583
  • 4
  • 34
  • 52