Codility "max slice swap" challenge
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] -&gt; [0, 1, 3, 6]
    partialSum = accumulate(data, operator.add)
    # rolling max: [4, 3, 2, 1] -&gt; [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] -&gt; [0, 1, 3, 6]
    partialSum = list(accumulate(data))
    # rolling max: [4, 3, 2, 1] -&gt; [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])