7
\$\begingroup\$

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)
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – phisheep Apr 19 '17 at 16:44
  • \$\begingroup\$ @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. \$\endgroup\$ – ChatterOne Apr 20 '17 at 6:55
  • \$\begingroup\$ @ChatterOne Ah, that makes more sense, thankyou . \$\endgroup\$ – phisheep Apr 20 '17 at 8:24
  • \$\begingroup\$ @phisheep: corrected it \$\endgroup\$ – Harsha Apr 20 '17 at 16:04
  • \$\begingroup\$ @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. \$\endgroup\$ – Janne Karila Apr 21 '17 at 9:05
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.