O(n) solution for finding maximum sum of differences python 3.x?

Question

I was wondering, given a list of integers, say l, and if we are allowed to select 3 integers from this list, say left, middle, right, where middle > left, right and left, middle, right appear in that order in the list (ie. index(left)<index(middle)<index(right)), does there exist an O(n) solution for finding the maximum of middle - left + middle - right? You may suppose that lists that do not satisfy these conditions do not appear (eg. [5, 0, 5] as pointed out by Eric Duminil)

Currently, I am able to come up with what I believe is (roughly) an O(n^2) solution (correct me if I am wrong).

Essentially, my current idea is to do:

maximum = 0
for idx in range(1, N - 1):
    left = min(l[0: idx])
    right = min(l[idx + 1:])
    middle = l[idx]

    if left < middle and right < middle:
        new_max = middle - left + middle - right
        maximum = max(new_max, maximum)

Help/hints would be greatly appreciated.

Thanks!

Answer 1

You can run through your numbers once, keeping a running minimum value, and storing it at each step, so that at the end you know what the minimum value is to the left of each index. That's O(n).

Similarly, you can run through all your numbers once from right to left, and work out what the minimum value is to the right of each index. That is O(n).

Then you can run through each possible middle value, and take the left and right values from your earlier computations. That is O(n).

O(n) + O(n) + O(n) = O(n).

Answer 2

The trick is that minimum value of the list is always the part of solution (either left, or right).

1. Find minimum of the list, which is O(n). Now this minimum element will be either left or right.
2. Find maximum of (2x-y), where idx(x) > idx(y), and idx(x) < idx(min), that is check the left part of the list
3. Find max(2x-y), where idx(x) < idx(y), and idx(x) > idx(min), that is check the right part of the list
4. Now take maximum of the steps 2 and 3, which is your left/middle (or right/middle).

Answer 3

Here's a way to calculate the minimums, left and right of every index, in O(n):

import random

N = 10
l = [random.randrange(N) for _ in range(N)]

print(l)
# => [9, 9, 3, 4, 6, 7, 0, 0, 7, 6]

min_lefts = []
min_left = float("inf")
min_rights = [None for _ in range(N)]
min_right = float("inf")

for i in range(N):
    e = l[i]
    if e < min_left:
        min_left = e
    min_lefts.append(min_left)

print(min_lefts)
# => [9, 9, 3, 3, 3, 3, 0, 0, 0, 0]

for i in range(N-1,-1,-1):
    e = l[i]
    if e < min_right:
        min_right = e
    min_rights[i] = min_right

print(min_rights)
# => [0, 0, 0, 0, 0, 0, 0, 0, 6, 6]

You can now iterate over every middle element in l (idx between 1 and N-2), and find the minimum of 2 * l[idx] - min_rights[idx] - min_lefts[idx]. This operation is also O(n):

print(max(2 * l[i] - min_rights[i] - min_lefts[i] for i in range(1, N-2)))

It outputs :

11

which is 2 * 7 - 0 - 3.

Answer 4

Here are some timings! Feel free to edit the code that does the timing and\add new entries.

from timeit import timeit


setup10 = '''
import numpy.random as nprnd
lst = list(nprnd.randint(1000, size=10))
'''

setup100 = '''
import numpy.random as nprnd
lst = list(nprnd.randint(1000, size=100))
'''

setup1000 = '''
import numpy.random as nprnd
lst = list(nprnd.randint(1000, size=1000))
'''

fsetup = '''

import sys

def f2(lst):
    N = len(lst)
    maximum = 0
    for idx in range(1, N - 1):
        left = min(lst[0: idx])
        right = min(lst[idx + 1:])
        middle = lst[idx]

        if left < middle and right < middle:
            new_max = middle - left + middle - right
            maximum = max(new_max, maximum)
    return maximum


def eric(lst):
    N = len(lst)
    min_lefts = []
    min_left = float("inf")
    min_rights = [None for _ in range(N)]
    min_right = float("inf")

    for i in range(N):
        e = lst[i]
        if e < min_left:
            min_left = e
        min_lefts.append(min_left)

    for i in range(N-1,-1,-1):
        e = lst[i]
        if e < min_right:
            min_right = e
        min_rights[i] = min_right

    return max(2 * lst[i] - min_rights[i] - min_lefts[i] for i in range(1, N-2))


def bpl(lst):
    res = -sys.maxsize
    a = sys.maxsize
    b = -sys.maxsize
    c = sys.maxsize

    for i, v in enumerate(lst[1:-1]):
        a = min(lst[i], a)
        c = min(lst[i + 2], c)
        b = max(lst[i], b)
        res = max(2 * b - a - c, res)
    return res


def meow(l):
    N = len(l)
    right_min = (N - 2) * [sys.maxsize]
    right_min[0] = l[N - 1]
    for i in range(3, N):
       right_min[i - 2] = min(right_min[i - 2], l[N - i + 1])
    left = l[2]
    maximum = 2*l[1] - left - right_min[N - 3]

    for idx in range(2, N - 1):
        left = min(left, l[idx-1])
        right = right_min[N - idx - 2]
        middle = l[idx]

        if left < middle and right < middle:
            new_max = middle - left + middle - right
            maximum = max(new_max, maximum)
    return maximum

'''


print('OP with 10\t:{}'.format(timeit(stmt="f2(lst)", setup=setup10 + fsetup, number=100)))
print('eric with 10\t:{}'.format(timeit(stmt="eric(lst)", setup=setup10 + fsetup, number=100)))
print('bpl with 10\t:{}'.format(timeit(stmt="bpl(lst)", setup=setup10 + fsetup, number=100)))
print('meow with 10\t:{}'.format(timeit(stmt="meow(lst)", setup=setup10 + fsetup, number=100)))
print()
print('OP with 100\t:{}'.format(timeit(stmt="f2(lst)", setup=setup100 + fsetup, number=100)))
print('eric with 100\t:{}'.format(timeit(stmt="eric(lst)", setup=setup100 + fsetup, number=100)))
print('bpl with 100\t:{}'.format(timeit(stmt="bpl(lst)", setup=setup100 + fsetup, number=100)))
print('meow with 10\t:{}'.format(timeit(stmt="meow(lst)", setup=setup100 + fsetup, number=100)))
print()
print('OP with 1000\t:{}'.format(timeit(stmt="f2(lst)", setup=setup1000 + fsetup, number=100)))
print('eric with 1000\t:{}'.format(timeit(stmt="eric(lst)", setup=setup1000 + fsetup, number=100)))
print('bpl with 1000\t:{}'.format(timeit(stmt="bpl(lst)", setup=setup1000 + fsetup, number=100)))
print('meow with 10\t:{}'.format(timeit(stmt="meow(lst)", setup=setup1000 + fsetup, number=100)))

---

10 elements on the list, 100 repetitions
OP      :0.00102
eric    :0.00117
bpl     :0.00141
meow    :0.00159

100 elements on the list, 100 repetitions
OP      :0.03200
eric    :0.00654
bpl     :0.01023
meow    :0.02011

1000 elements on the list, 100 repetitions
OP      :2.34821
eric    :0.06086
bpl     :0.10305
meow    :0.21190

---

And as a bonus an inefficient one-liner:

maximum = max(2*z -sum(x) for x, z in zip([[min(lst[:i+1]), min(lst[i+2:])] for i, _ in enumerate(lst[:-2])], lst[1:-1]))

Answer 5

possible solution:

import sys
import random

random.seed(1)

l = [random.randint(0, 100) for i in range(10)]
print(l)

res = -sys.maxsize
a = sys.maxsize
b = -sys.maxsize
c = sys.maxsize

for i, v in enumerate(l[1:-1]):
    a = min(l[i], a)
    c = min(l[i + 2], c)
    b = max(l[i], b)
    res = max(2 * b - a - c, res)

print(res)

output:

[13, 85, 77, 25, 50, 45, 65, 79, 9, 2]
155

Answer 6

You are definitely on the right track, you just have to get rid of those min operations. So my hint for you is that you can pre-compute them (in linear time) beforehand, then look up the min in the loop, as you are already doing.

To clarify: you have to pre-compute min(list[0:i]) and min(list[i:n]) for all i's, before the part you already have. The idea is to store them in two arrays, say m1 and m2, such that m1[i] = min(list[0:i]) and m2[i] = min(list[i:n]). Then, use m1 and m2 in your loop

The challenge now is to compute m1 and m2 in linear time, meaning that you are not allowed to use the min function to compute them. If you have m1[i], how can you compute m1[i+1] using list[i+1]?