Codility "max slice swap" challenge

Question

Problem Description:

Find the maximum sum of a compact subsequence of array elements after performing a single swap operation.

Solution:

def maxsum(lst): # Get maximum sum of all possible slices in list
    max_ending = max_slice = lst[0]
    for i in xrange(1,len(lst)):
        max_ending = max(lst[i], max_ending + lst[i])
        max_slice = max(max_slice, max_ending)
    return max_slice

def solution(A):
    msum = A[0]
    for i in xrange(0, len(A)-1):
        for j in xrange(i+1, len(A)):
            A[i], A[j] = A[j], A[i] # swap
            msum = max(maxsum(A),msum)
            A[i], A[j] = A[j], A[i] # swap back
    return msum

I am swapping all possible pairs in the list to get the maximum sum after a particular swap and then the maximum of all those maximum sums. Given the \$O(N^3)\$ complexity, it times out for larger sequences/values. Is there a better way to implement this solution? Codility says \$O(N)\$ is possible.

Answer 1

After reading through the article linked in Josay's comment, I have translated the code into Python, removed extra fluff and added a bunch of comments to make it more readable then the version in the article. It also ran faster than the solution offered, probably due to Python's highly optimized Lists vs Java's ArrayLists.

This solution is \$O(N)\$ in both space and time, and for more details on why it works, refer to the article.

Here it is for Python 2.7 (the version required for Codility):

import operator

def solution(A):
    # calculate best swap forwards
    result1 = calculate(A)
    # calculate best swap backwards
    A.reverse()
    result2 = calculate(A)

    result = max(result1, result2)

    # If list is negative, choose least negative value
    if result == 0:
        return max(data)

    return result


def calculate(data):
    """Calculates the best partial sum swapping from front of data to back"""
    n = len(data)
    total = sum(data)

    # rolling sum: [0, 1, 2, 3] -> [0, 1, 3, 6]
    partialSum = accumulate(data, operator.add)
    # rolling max: [4, 3, 2, 1] -> [4, 4, 4, 4]
    partialMax = accumulate(data, max)

    differences = [partialSum[i] - partialMax[i] for i in range(n)]
    # rolling minimum of differences
    minDifferences = accumulate(differences, min)

    # Calculate best forward partial sums
    list1 = [min(data[0], 0)]
    for i in range(1, n):
        list1.append(min(minDifferences[i-1] + data[i], list1[i-1]))

    # Calculate best reverse partial sums
    data.reverse()
    reversedPartialSum = accumulate(data, operator.add)
    list2 = accumulate(reversedPartial, min)
    list2.reverse()

    # Calculate best swap result

    best = 0
    for i in range(n-1):
        best = max(best, total - list1[i] - list2[i+1])

    return max(best, total - list1[n-1])


def accumulate(values, function):
    """Accumulates the results of the function into a list"""
    result = [values[0]]
    for i in range(1, len(values)):
        result.append(function(values[i], result[i-1]))
    return result

And just for fun, here's a Python3.x version with the new accumulate() function from itertools:

from itertools import accumulate

def solution(A):
    # calculate best swap forwards
    result1 = calculate(A)
    # calculate best swap backwards
    A.reverse()
    result2 = calculate(A)

    result = max(result1, result2)

    # If list is negative, choose least negative value
    if result == 0:
        return max(data)

    return result

def calculate(data):
    """Calculates the best partial sum swapping from front of data to back"""
    n = len(data)
    total = sum(data)

    # rolling sum: [0, 1, 2, 3] -> [0, 1, 3, 6]
    partialSum = list(accumulate(data))
    # rolling max: [4, 3, 2, 1] -> [4, 4, 4, 4]
    partialMax = list(accumulate(data, max))

    differences = [partialSum[i] - partialMax[i] for i in range(n)]
    # rolling minimum of differences
    minDifferences = list(accumulate(differences, min))

    # Calculate best forward partial sums
    list1 = [min(data[0], 0)]
    for i in range(1, n):
        list1.append(min(minDifferences[i-1] + data[i], list1[i-1]))

    # Calculate best reverse partial sums
    data.reverse()
    reversedPartialSum = list(accumulate(data))
    list2 = list(accumulate(reversedPartial, min))
    list2.reverse()

    # Calculate best swap result

    best = 0
    for i in range(n-1):
        best = max(best, total - list1[i] - list2[i+1])

    return max(best, total - list1[n-1])

Answer 2

I found the thinking laid out in the blog post posted in Josay's comment to be somewhat convoluted. This Quora answer here lays out a much clearer method of thinking about the problem, and I wrote code based on it.

During the iteration, you're fixing the element that is going to be swapped, and swapping it with the best option to the right in the list. You do this with the input data forward and reversed, then combine the results to get the optimal answer.

def add_zeroes(l):
    return [0] + l + [0]

def solution(A):
    left_sums, left_slice_elt_pairs = calc(A) 
    right_sums, right_slice_elt_pairs = calc(list(reversed(A)))
    left_sums = add_zeroes(left_sums)
    right_sums = add_zeroes(list(reversed(right_sums)))
    left_slice_elt_pairs = add_zeroes(left_slice_elt_pairs)
    right_slice_elt_pairs = add_zeroes(list(reversed(right_slice_elt_pairs)))
    best = []
    for i in range(1,len(A)+1):
        best.append(max(left_sums[i-1] + right_slice_elt_pairs[i+1], left_slice_elt_pairs[i-1] + right_sums[i+1]))
    best.append(sum(A))
    sol = max(best)
    if sol == 0 and 0 not in A:
        return max(A)
    return sol

def calc(A):
    left_sums = [max(A[0], 0)]
    for i in range(1,len(A)):
        left_sums.append(max(left_sums[i-1] + A[i], 0))
    max_to_left = [0]
    for i in range(1,len(A)):
        max_to_left.append(max(max_to_left[i-1], A[i-1]))
    left_slice_elt_pairs = [max(A[0], 0)]
    for i in range(1,len(A)):
        left_slice_elt_pairs.append(max([left_slice_elt_pairs[i-1]+A[i], max_to_left[i], max_to_left[i] + A[i]]))
    return left_sums, left_slice_elt_pairs