Codility "max slice swap" challenge

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.

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])

StackExchange Code Review Q#58146, answer score: 3