Find an idx with the maximum sum

Question

So I need to write an a recursive program that returns an index so that the sum of the elemnts up to it is maximum. For example the list [1,-5,9,-12,3,3,3,2], the idx with the maximum sum of the elements is 2. Another example: The list [1,-5,9,7], the idx that will be return is 3 in this case. If someone know how to do it, or know an a similar question that someone asked in the forum, it’ll be helpful. Thanks

StackOverflow is not a code-writing service. Please show the code you tried, and describe where you're getting stuck. — Thomas, Feb 24 '21 at 11:07
Does this answer your question? [Python Finding Index of Maximum in List](https://stackoverflow.com/questions/11530799/python-finding-index-of-maximum-in-list) — Sayandip Dutta, Feb 24 '21 at 11:08
This is a constrained instance of the [Maximum Subsequence Sum Problem](https://en.wikipedia.org/wiki/Maximum_subarray_problem) of which there are a few solutions. A divide and conquer and thus recursive version you can find [here](http://www.cs.cmu.edu/afs/cs/academic/class/15210-f13/www/lectures/lecture04.pdf) though in pseudocode rather than python. The discussion there should give you an idea of how to come up with your own solution to the constrained case. — Ezequiel Muns, Feb 24 '21 at 16:27

score 0 · Answer 1 · answered Feb 24 '21 at 11:12

you need to input a lower estimate for the sum, which is why I used min(list_of_numbers)*100. You may need to modify it, if you can use numpy, I would recommend replacing that value with -np.inf

list_of_numbers = [1,-5,9,-12,3,3,3,2]

def maxSumId(list_of_numbers):
    id_max = 0
    sumVal = 0
    maxVal = min(list_of_numbers)*100
    for i,number in enumerate(list_of_numbers):
        sumVal += number
        if sumVal > maxVal:
            maxVal = sumVal
            id_max = i
    return id_max
    
maxSumId(list_of_numbers)

This gives the right solution, but isn't recursive. – Ezequiel Muns Feb 24 '21 at 16:37 — Ezequiel Muns, Feb 24 '21 at 16:37

score 0 · Answer 2 · answered Feb 28 '21 at 19:26

Your recursion can easily compute the cumulative sum but it will need to carry the maximum and its index along in order to return an index rather than a value.

# L:list, i:current index, s:current sum, mi:max sum index, ms:max sum value

def iMaxSum(L,i=0,s=0,mi=0,ms=None):
    if i>=len(L): return mi           # end of list return max index
    if ms is None or L[i]+s>ms:       # track max sum and its index 
        ms,mi = s + L[i],i
    return iMaxSum(L,i+1,s+L[i],mi,ms) # next item,index,sum

    
print(iMaxSum([1,-5,9,-12,3,3,3,2])) # 2
print(iMaxSum([1,-5,9,7]))           # 3

Find an idx with the maximum sum

2 Answers2