Array subset division with equal sums Today I stumbled upon a problem which looked like the partition problem but certainly is different.

Given array of positive integers, guaranteed to not be divisible into two continious subsets of equal sum, remove a ceratin continious subset to form two subsets of equal sum.

Example:


Array: 7 5 9 1 3 9 6 
Remove elements 9 and 1 to form array 7 5 3 9 6  that is divisible
into two subarrays of equal sum {7,5,3} and {9,6}


Another example:


Array: 1 10 100
Whichever subset to remove in the second case, it is not possible
to split the array into two parts with the same sum.


The limits for the array are 8000 elements and each element can be 1 bilion in size.

I'am just looking for algorithm help as I thought this was a variation of the partition problem and tried for some time to solve it, but i figured out it's beyond my knowledge. Any kind of help would be appreciated.
Let S denote the solution sum.  Besides the trivial O(1) solution with S=0, other solutions if any can be found by an easy O(n2) method.  Let A denote a given array of positive integers.  Consider two kinds of partitions of A:  (B, C, E, D) and (F, E, G, H), where each letter represents a sequential part of A, with A=B+C+E+D or A=F+E+G+H; C or G possibly empty; with E representing the extracted sequence.  We suppose a solution has either S = sum(B) = sum(C+D) = (sum(A)-sum(E))/2 or S = sum(F+G) = sum(H) = (sum(A)-sum(E))/2, and claim that any solution has either an intact prefix or an intact suffix, or both, uninterrupted by extraction E.

To test for a solution of the first kind:  Let S be a prefix sum of A.  We look for a solution for S by advancing the beginning of E through A, and after each advance, solving (at O(1) amortized cost) for the end of E.  With O(n) prefix sums and O(n) beginnings-of-E, overall cost is O(n2).

Testing for solutions of the second kind is analogous.  The lightly-tested program shown below does this step by testing reversed(A).

#!/usr/bin/env python3
# Program written by James Waldby on 16 June 2019
# re: https://cs.stackexchange.com/questions/101950,
# "Array subset division with equal sums"
# Copyright © 2019 by James Waldby.  Offered without warranty under
# GPL v3 terms as at http://www.gnu.org/licenses/gpl.html

def findPrefixSol(A):
    S=0; U=sum(A); H=U//2; n=len(A); print (A)
    for i in range(n):        # prefix = first i elements
        S += A[i]
        if S&gt;H: break
        Esum = 0                # sum of extract E
        Etarget = U - 2*S       # required size of E
        k = i+1                 # k -&gt; after last element of E
        for j in range(i+1, n-1): # j -&gt; first element of E
            while Esum &lt; Etarget and k&lt;n-1:
                Esum += A[k]
                k += 1
            if Esum &gt; Etarget:
                Esum -= A[j]    # remove first element of E
                continue        # go try next E
            if Esum &lt; Etarget:
                break           # can't extract enough to win; advance i
            print('Sol. for partition {}...{}...:  S={}, Es={}, U={}'.format(A[:i+1], A[j:k], S, Esum, U))
            break

A=[7, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))
print()
A=[7, 5, 9, 1, 5, 9, 1, 3, 9, 9, 1, 5, 9, 1, 3, 9, 6]
findPrefixSol(A)
findPrefixSol(list(reversed(A)))