Finding the consecutive sums of an array

user_8124392 0
Viewed 910

I am working through a coding challenge. The challenge basically wants me to find the max sum of its k consecutive elements. Here is an example:

For inputArray = [2, 3, 5, 1, 6] and k = 2, the output should be arrayMaxConsecutiveSum(inputArray, k) = 8. All possible sums of 2 consecutive elements are:

2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.

Thus, the answer is 8.

This is my attempt. I looked at the consecutive sum as sub-lists. So if I have k=3, then I have to add the 2 elements following i. So if the beginning is index 0, then the end is beginning + k-1. Then I tried to use a for loop to append the sum of every k chunks to a new list. My end goal was to return the max() from this list:

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + (k-1)
    sum_list = []
    
    for i in range(0, len(inputArray)):
        begin = i
        sum_list.append(sum(inputArray[begin:end+1]))
    
    print(sum_list)

Now I just wanted to see what my sum_list looked like before I tried to return its max. However, this is what it returns for a test case:

Input: inputArray: [2, 3, 5, 1, 6]
k: 2
Output: null
Expected Output: 8
Console Output: [5, 3, 0, 0, 0]

I think my logic is correct. I would just like to know where it is that I am making a mistake.

algorithm python
4 Answers

A fairly efficient solution is to use itertools.islice and zip for generating groups of consecutive elements. This removes the need for slicing your list

consecutive_elements = zip(*(islice(inputArray, x, None) for x in range(k)))

An example of what the islice generator produces:

>>> [list(islice(range(5), x, None)) for x in range(3)]
[[0, 1, 2, 3, 4], [1, 2, 3, 4], [2, 3, 4]]

islice(inputArray, x, None) for x in range(k) creates iterables from your input that slice off increasing numbers of elements, passing this to zip then joins the iterables element wise creating your groups

And then use map to generate the sums rather than creating an intermediary list

return max(map(sum, consecutive_elements))
user_5485620

If you want something more readable and without using any other libraries such as itertools, you can try this one-liner -

[sum(i) for i in zip(*(inputArray[i:] for i in range(k)))]

[5, 8, 6, 7]

Debugging your code :

There are a few things wrong in the code. First, you are defining the end outside the loop. As begin change you want the end to change in the loop as well. Also, since python already considers n-1 index for end, you just need to set it to begin+k and not begin+(k-1). Next, you need to move the iterator from 0 to length or array - 1 as the last item will be just a single element. If you want to see where you have gone wrong, I have modified the code to run as you expect it to -

def arrayMaxConsecutiveSum(inputArray, k):
    #begin = 0 #<--- #No need since you are setting it to i in loop
    #end = begin + k #<--- Not to be defined here but inside loop
    sum_list = []
    
    for i in range(0, len(inputArray)-1): #<----
        begin = i
        end = begin + k #<--- 
        sum_list.append(sum(inputArray[begin:end])) #<----
    
    print(sum_list)

[5, 8, 6, 7]
user_47559540

take the sum from given index to index + k for (5 -(k-1)) times in this case and the max

inputArray = [2, 3, 5, 1, 6]
k = 3
print(max([sum(inputArray[idx : idx + k]) for idx in range(len(inputArray)-(k-1))]))
user_116225080

You need to update your ending index.

def arrayMaxConsecutiveSum(inputArray, k):
    begin = 0
    end = begin + k
    sum_list = []

    for i in range(0, len(inputArray)):
    
        sum_list.append(sum(inputArray[i:i + k]))

    print(sum_list)
user_121307430
Related