Buggy python submission (verdict: Time Limit Exceeded):
def diffarray(arr):
    sum = 0
    tmp = arr[0]
    for digit in arr[1:]:
        sum += abs(tmp - digit)
        tmp = digit
    return sum

def neighbor_diff(i, arr):
    if i == 0:
        return abs(arr[i] - arr[i+1])
    if i == len(arr) - 1:
        return abs(arr[i-1] - arr[i])
    else:
        return abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])

def swap_arr(arr, i, j):
    tmp_i = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp_i
    return


def search_diff(i,j,arr):
    '''
    数列arrのi番目とj番目をスワップさせた場合の差の総量の変化
    :return: 変化量
    '''
    tmp = - neighbor_diff(i, arr) - neighbor_diff(j, arr)

    swapped_arr = arr[:]
    swap_arr(swapped_arr, i, j)

    tmp += neighbor_diff(i, swapped_arr) + neighbor_diff(j, swapped_arr)
    return tmp

def change(arr):
    '''

    :param arr: 検証元の数列
    :return: 検証した結果見つかった最も差が大きい数列
    '''
    ret_arr = arr[:]

    for i in range(0, len(arr)):
        for j in range(i, len(arr)):
            henka = search_diff(i, j, arr)
            if henka > 0:
                swap_arr(arr,i,j)
            #print(i,j,henka,max,arr,swapped_arr)
    return True

def main():
    N = int(input())
    arr=[]
    for i in range(N):
        arr.append(int(input()))
    arr.sort()

    mid, mod = divmod(N, 2)

    start_arr = []
    for i in range(mid):
        start_arr.append(arr[i])
        start_arr.append(arr[-i-1])
    if mod == 1:
        start_arr.append(arr[mid])

    assert(len(arr) == len(start_arr))
    while True:
        nochange = change(start_arr)
        if nochange:
            break

    #print(start_arr,diffarray(start_arr[1:-1]))
    print(diffarray(start_arr))
    return


main()

Fixed submission:
def main():
    N = int(input())
    array = [int(input()) for _ in range(N)]
    array.sort()

    div, mod = divmod(N, 2)
    if mod == 0:
        fore, last_in_fore, first_in_rear, rear = array[:div-1], array[div-1], array[div], array[div+1:]

        a = 2 * sum(rear) + first_in_rear - last_in_fore - 2 * sum(fore)
        print(a)
        return
    else:
        #mode1 (mrfrm):(1,2,-2,2,1)
        array1=array[:]
        fore1=[]
        rear1=[]
        while True:
            fore1.append(array1.pop(0))
            if len(array1) <= 2:
                break
            rear1.append(array1.pop(-1))
        mid1 = array1
        a1 = 2 * sum(rear1) + sum(mid1) - 2 * sum(fore1)

        #mode2 (mfrfm):(1,-2,2,-2,1)
        array2 = array[:]
        fore2=[]
        rear2=[]
        while True:
            rear2.append(array2.pop(-1))
            if len(array2) <= 2:
                break
            fore2.append(array2.pop(0))
        mid2 = array2
        a2 = 2 * sum(rear2) - sum(mid2) - 2 * sum(fore2)

        print(max(a1, a2))
        return
    return


main()

Buggy python submission (verdict: Time Limit Exceeded):

def main():

    def diffarray(arr):
        sum = 0
        tmp = arr[0]
        for digit in arr[1:]:
            sum += abs(tmp - digit)
            tmp = digit
        return sum

    def neighbor_diff(i, arr):
        if i == 0:
            return abs(arr[i] - arr[i+1])
        if i == len(arr) - 1:
            return abs(arr[i-1] - arr[i])
        else:
            return abs(arr[i-1] - arr[i]) + abs(arr[i] - arr[i+1])

    def swap_arr(arr, i, j):
        tmp_i = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp_i
        return


    def search_diff(i,j,arr):
        '''
        数列arrのi番目とj番目をスワップさせた場合の差の総量の変化
        :return: 変化量
        '''
        tmp = - neighbor_diff(i, arr) - neighbor_diff(j, arr)

        swapped_arr = arr[:]
        swap_arr(swapped_arr, i, j)

        tmp += neighbor_diff(i, swapped_arr) + neighbor_diff(j, swapped_arr)
        return tmp, swapped_arr

    def change(arr):
        '''

        :param arr: 検証元の数列
        :return: 検証した結果見つかった最も差が大きい数列
        '''
        ret_arr = arr[:]

        max = 0
        mem_i = -1
        mem_j = -1

        for i in range(0, len(arr)):
            for j in range(i, len(arr)):
                henka, swapped_arr = search_diff(i, j, arr)
                if henka > max:
                    ret_arr = swapped_arr
                    max = henka
                    mem_i = i
                    mem_j = j
                #print(i,j,henka,max,arr,swapped_arr)

        if max == 0:
            return False
        swap_arr(arr, mem_i, mem_j)
        return True



    N = int(input())
    arr=[]
    for i in range(N):
        arr.append(int(input()))
    arr.sort()

    mid, mod = divmod(N, 2)

    start_arr = []
    for i in range(mid):
        start_arr.append(arr[i])
        start_arr.append(arr[-i-1])
    if mod == 1:
        start_arr.append(arr[mid])

    assert(len(arr) == len(start_arr))
    while True:
        ret_arr = change(start_arr)
        if not ret_arr:
            break

    #print(start_arr,diffarray(start_arr[1:-1]))
    print(diffarray(start_arr))
    return


main()

Fixed submission:
def main():
    N = int(input())
    array = [int(input()) for _ in range(N)]
    array.sort()

    div, mod = divmod(N, 2)
    if mod == 0:
        fore, last_in_fore, first_in_rear, rear = array[:div-1], array[div-1], array[div], array[div+1:]

        a = 2 * sum(rear) + first_in_rear - last_in_fore - 2 * sum(fore)
        print(a)
        return
    else:
        #mode1 (mrfrm):(1,2,-2,2,1)
        array1=array[:]
        fore1=[]
        rear1=[]
        while True:
            fore1.append(array1.pop(0))
            if len(array1) <= 2:
                break
            rear1.append(array1.pop(-1))
        mid1 = array1
        a1 = 2 * sum(rear1) + sum(mid1) - 2 * sum(fore1)

        #mode2 (mfrfm):(1,-2,2,-2,1)
        array2 = array[:]
        fore2=[]
        rear2=[]
        while True:
            rear2.append(array2.pop(-1))
            if len(array2) <= 2:
                break
            fore2.append(array2.pop(0))
        mid2 = array2
        a2 = 2 * sum(rear2) - sum(mid2) - 2 * sum(fore2)

        print(max(a1, a2))
        return
    return


main()