find the subarray where the square of the difference of the elements at even and odd places in that subarray is maximal

Somewhere on HackerRank I saw a problem: find the subarray where the square of the difference of the elements at even and odd places in that subarray is maximal.

Now I can't find this problem there.

The Force method requires about n**3/6 = O(n**3) operations. The method based on DP ideas is about n**2/2 = O(n**2). The code below. I'm currently trying to think of something more efficient based on the divide-and-conquer approach, but I can't complete the algorithm. My existing code seems to me to be erroneous.

May be someone can tell me where to dig further or give me a useful link? Or maybe this problem has already been discussed? Unfortunately I can't find anything suitable.

Thanks.

'''
find subarray with max (sum(odd) - sum(even))**2
'''
#-------------------------------------------------------------------------------
def maxsum(arr): #O(n^3 / 6)
    iter=0
    n= len(arr)
    mx = 0
    for start in range(n):
        d = arr[start]
        d*=d
        if d > mx: mx=d
        for leni in range(1,n-start):
            sub = arr[start:start+leni+1]
            ns = len(sub)
            sum0, sum1 = 0, 0
            for i in range(ns):
                if i %2 ==0: sum0+=sub[i]
                else: sum1 += sub[i]
                iter+=1
            tmp = sum0-sum1
            tmp*=tmp
            if tmp > mx: mx = tmp
    return mx,iter
#-------------------------------------------------------------------------------
def maxsum1(arr): #O(n^2 / 2)
    iter=0
    n= len(arr)
    mx = 0
    for start in range(n):
        d = arr[start]
        d*=d
        if d > mx: mx=d
        sum0, sum1 = 0, 0
        for leni in range(n-start):
            i = start+leni
            c = arr[i]
            if i %2 ==0: sum0 += c
            else: sum1 += c
            iter+=1
            tmp = sum0-sum1
            tmp*=tmp
            if tmp > mx: mx = tmp
    return mx,iter
#-------------------------------------------------------------------------------
iter=0
def maxx(arr):
    global iter
    n= len(arr)
    sum0, sum1 = 0, 0
    for i in range(n):
        c = arr[i]
        if i%2==0: sum0 += c
        else: sum1 += c
        iter+=1
    d = sum0-sum1
    d*=d
    return d


def maxsum2(arr): #O(1.4*n*ln n + 2*n)
    global iter
    n= len(arr)
    mx = 0
    if n==1:
        iter+=1
        return arr[0]*arr[0]
    if n==2:
        d0 = arr[0]*arr[0]
        d1 = arr[1]*arr[1]
        d2 = arr[0] - arr[1]
        d2*=d2
        iter+=6
        return max(d0,d1,d2)
    d0 = maxsum2(arr[:n//2])
    d1 = maxsum2(arr[n//2:])
    d2 = maxx(arr)
    res = max(d0,d1)
    res = max(res,d2)
    return res
#-------------------------------------------------------------------------------
def main():
    arr = [1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5,1,-2,3,-4,5]
    print(len(arr))
    print(maxsum(arr))
    print(maxsum1(arr))
    print(maxsum2(arr),iter)