Replace an element of a list to get maximum sum of subsequence
It's actually a really nice programming quiz.



You tried to implement a linear (\$\mathcal{O}(n)\$ time) solution, and this is the correct final aim, but, I think, you agree that the current solution is hard to understand especially without any comments.

So let's start from something easy-to-understand and not very efficient. But this will allow us to check a correctness of your solution in a first place.

Brute-force solution (\$\mathcal{O}(n^2)\$ time)

It is clear that this task is related to the maximum subarray problem except the condition of replacing by N. So let's make a loop through all positions of the original array; on every iteration let's replace the current element of the array by N and find the largest sum by Kadane's algorithm.

'''
Kadane's algorithm for the Maximum subarray problem
Returns maximum sum
'''
def max_subarray(arr):  
    max_sum = -sys.maxint
    cur_sum = 0
    for a in arr:
        cur_sum += a
        max_sum = max(cur_sum, max_sum)
        cur_sum = max(cur_sum, 0)
    return max_sum

def find_replaceable_element0(arr, n):
    max_sum = arr[0]
    max_sum_index = 0
    cur_sum = 0
    for i, a in enumerate(arr):
        arr[i] = n #replace by N in position i
        cur_sum = max_subarray(arr)
        arr[i] = a #change back
        if (cur_sum &gt; max_sum or
                (cur_sum == max_sum and arr[max_sum_index] &gt; arr[i])): #find the smallest
            max_sum = cur_sum
            max_sum_index = i
    return arr[max_sum_index], max_sum


Now we can check correctness of your solution.

import random
random.seed(123)
for i in range(10000):
    arr = random.sample(range(-10, 10), 5)
    n = random.randint(-5, 5)
    if (find_replaceable_element0(arr, n) != find_replaceable_element(arr, n)):
        print(find_replaceable_element0(arr, n))
        print(find_replaceable_element(arr, n))
        print(arr, n)
        break


And for this parameters L = [-9, 9, -3, 8, 4], N = -5 your solution gives M = -3, S = 16. That's wrong because changing -9 on N you can get S = 18.



For sure this task can be solved in \$\mathcal{O}(n)\$ time and \$\mathcal{O}(1)\$ additional memory, but extensive testing should be priority number one.