Replace an element of a list to get maximum sum of subsequence

Question

I was practicing for interview questions, and my friend recommended this one:

Given an initial list of integers L, and a number N, find the smallest member M of L, which on being replaced by N, gives the subsequence with the largest sum S for any subsequence within the modified list.

Examples:

L = [1, 2, -1, 3, 4], N = 4 => M = -1, S = 14

L = [1, 2, 3, 4], N = 4 => M = 1, S = 13

L = [4, 4, 4, 4], N = 4 => M = 4, S = 16

L = [1, 2, 10, -3, -10, 8, 5], N = 4 => M = -10, S = 27

L = [1, 3, 2, -1, 4], N = -2 => M=-1, S = 8

How can I improve this code?

def find_replaceable_element(arr, n):
    max_sum = [0] * len(arr)
    low = [-10000] * len(arr)
    current_sum = 0
    for index, val in enumerate(arr):
        current_sum += val
        max_sum[index] = max(current_sum, val)
        if index >= 1:
            if low[index-1] > val:
                low[index] = val
            else:
                low[index] = low[index-1]
        else:
            low[index] = val

        if val > current_sum:
            current_sum = val
            low[index] = val
    print low
    print max_sum
    max_got = 0
    lowest = 0
    for i, val in enumerate(max_sum):
        cur_max = max_sum[i] - low[i] + n
        if max_got < cur_max:
            max_got = cur_max
            lowest = low[i]
    return lowest, max_got

arr = [1, 2, 10, -3, -10, 8, 5]
print find_replaceable_element(arr, 8)

Answer 1

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 > max_sum or
                (cur_sum == max_sum and arr[max_sum_index] > 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.