Find a subset of length 4 which has a maximum value of sum [closed]

Tags:



So I need a solution for this example without using queue. For example [1, 5, 7, 2, 11, 3, 6, 15, 1, 5, 0, 7, 6, 3] max sum of 4 elements here is 35 [11, 3, 6, 15]. This is my ‘logical’ code but I don’t know why is not working.

array = [1, 5, 7, 2, 11, 3, 6, 15, 1, 5, 0, 7, 6, 3]

k = 4
current_sum = 0
max_sum = -1
n = len(array)

for i in range(n):
    for j in range(i, n):
        if j < k:
            current_sum += array[j]
            continue
        
        
        if current_sum > max_sum: 
            max_sum = current_sum            


print(f"Max sum is {max_sum}")

Answer

Other answers have given correct solutions to your problem, but I’m going to go over why your code isn’t working.

if j < k:

If your code was working properly you’d expect j to be 0, 1, 2, 3 on the first time through the outer loop, then 1, 2, 3, 4 on the second time, etc. This means you shouldn’t be comparing j to k, you should be comparing j to i+k.

continue

In general, continue shouldn’t be used when possible. It makes the flow of the code hard to follow. Instead of using continue I’m going to change a different part of your code:

for j in range(i, n):

It makes sense that you’re starting at i, but why are you going to n? If you only want j to be 4 numbers, you should stop it at those 4 numbers. Let’s change this to for j in range(i, i+k):

Now we just need to make a couple more changes. You don’t want to check current_sum before you’re done adding it up, so let’s put if current_sum > max_sum inside the outer for loop. And don’t forget to reset current_sum to 0 after each iteration through the outer loop!

Lastly, we need to make sure we don’t go out of range of the array. We’ll do this by changing for i in range(n): to for i in range(n-k):.

The final code:

array = [1, 5, 7, 2, 11, 3, 6, 15, 1, 5, 0, 7, 6, 3]

k = 4
current_sum = 0
max_sum = -1
n = len(array)

for i in range(n-k):
    for j in range(i, i+k):
        current_sum += array[j]
        
    if current_sum > max_sum: 
        max_sum = current_sum
    current_sum = 0

print(f"Max sum is {max_sum}")

There are still some problems with this code, like when array has a length less than 4, but this fixes all the initial problems you had.



Source: stackoverflow