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 = 14L = [1, 2, 3, 4], N = 4
=>
M = 1, S = 13L = [4, 4, 4, 4], N = 4
=>
M = 4, S = 16L = [1, 2, 10, -3, -10, 8, 5], N = 4
=>
M = -10, S = 27L = [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)
7, 6, 6 = 19
as the highest subsequence sum butN
is5
, that would probably not be the highest anymore. If you take the subsequence sum7, 8, 3 = 18
, that may not be the highest sum, but replacing3
withN = 5
, it would become7, 8, 5 = 20
which is now the highest sum. So the problem here is whenN
is less than the minimum in the subsequence. \$\endgroup\$