I'm currently studying algorithms in pseudocode and when I attempted to convert it into python I've come across a few issues that I was curious about.
In pseudocode the algorithm is:
Algorithm-1(A:array[1..n] of integer) sum,max:integer
sum = 0
max = 0
for i = 1 to n
sum = 0
for j = i to n
sum = sum + A[j]
if sum > max then
max = sum
return max
The problem in question is running through the following arrays: [1,2,3,4,5,6,7,8,9,10], [-1,-2,-3,-4,-5,-6,-7,-8,-9,-10], [0,0,0,0,0,0,0,0,0,0,0], [-1,2,-3,4,-5,6,7,-8,9,-10] and finding the return value. I can see that the output for the first 3 should be as follows: 54, 0, 0 but the 4th one is where I'm having trouble.
My understanding of this algorithm is that it takes the base array, finds its sum, and then takes the same array starting at the next index and finds that sum, and the value that's returned is the highest of these sums.
Basically if given the array of [1,2,-3,4,5] it looks at it this way:
Sum of [1,2,-3,4,5] = 9
Sum of [2,-3,4,5] = 8
Sum of [-3,4,5] = 6
Sum of [4,5] = 9
Sum of [5] = 5
And the final max value returned is 9.
Based on this understanding, I'm thinking that the value of the 4th array is 4 from [6,7,-8,9,-10]. Would that be correct?
Now moving onto my second question, how could this pseudocode be properly replicated in Python?
What I've come up with that doesn't quite work is:
def testFunction(array):
sum = 0
max = 0
for i in array:
sum = 0
j = i
for j in range(j, len(array)):
arrayVal = array[j] #redundant but for debug purposes
sum = sum + arrayVal
if sum > max:
max = sum
return max
I am a little bit rusty in Python but I've never come across the issue of changing the range that a for loop operates on so I was wondering how I would properly convert the code. Also upon looking at my debugger it seems that the iterator, i or j in this case doesnt seem to be the index but it is instead the value associated with that index, which is messing up the range portion of my second loop.
This is obviously a homework question and I've found a lot of mixed answers on this exact scenario so I tried to convert it into Python but this opened up another bag of problems so I wanted to come here for advice and a potential solution.
I hope I've been clear enough.
Thanks!
If you're trying to find the max sum of consecutive members from the list without using built-in function sum and max, here is a possible solution.
def testFunction(array):
s = 0
for i in array:
s += i
mx = s
print('The sum of {} is: {}'.format(array, s))
k = 1
for i in array[:-1]:
s -= i
print('The sum of {} is: {}'.format(array[k:], s))
mx = mx if s < mx else s
k += 1
return mx
print(testFunction([1, 2, -3, 4, 5]))
The output is
The sum of [1, 2, -3, 4, 5] is: 9
The sum of [2, -3, 4, 5] is: 8
The sum of [-3, 4, 5] is: 6
The sum of [4, 5] is: 9
The sum of [5] is: 5
9