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

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)

• Your code does not reproduce four of the five examples you give. So either I don't understand the question or the code is wrong. It seems to simply return min(L), sum(L)-M+N but surely it can't be that easy? Would appreciate some clarification. Apr 19, 2017 at 16:44
• @phisheep The question asks to find the subsequence where if you replace the minimum element, it has the highest sum among all subsequences. So, if you have the subsequence 7, 6, 6 = 19 as the highest subsequence sum but N is 5, that would probably not be the highest anymore. If you take the subsequence sum 7, 8, 3 = 18, that may not be the highest sum, but replacing 3 with N = 5 , it would become 7, 8, 5 = 20 which is now the highest sum. So the problem here is when N is less than the minimum in the subsequence. Apr 20, 2017 at 6:55
• @ChatterOne Ah, that makes more sense, thankyou . Apr 20, 2017 at 8:24
• @phisheep: corrected it Apr 20, 2017 at 16:04
• @MathiasEttinger The example at the end of code has N=8 while the similar example in the text has N=4. The code seems to give correct results for the examples in the text. Apr 21, 2017 at 9:05

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.