Find the largest continuous sum so that its minimum and its complement are the largest

Question

I have been given a sequence of numbers a_1,a_2,...,a_n. This amount is equal S=a_1+a_2+...+a_n, and I need to find a subsequence a_i,...,a_jsuch that it min(S-(a_i+...+a_j),a_i+...+a_j)is the maximum possible (both amounts must be nonempty).

Example:

1,2,3,4,5sequence 3,4, because then min(S-(a_i+...+a_j),a_i+...+a_j)=min(8,7)=7(and this is the maximum possible that can be checked for other subsequences).

I tried to do this with difficulty.

I load all the values ​​into an array tab[n].

I do it n-1once tab[i]+=tab[i-j]. So that tab[j]represents the amount from the beginning to j.

I check all possible amounts a_i+...+a_j=tab[j]-tab[i-1]and subtract it from the amount, take a minimum and see if it is more than before.

Required O(n^2). It makes me very sad and unhappy. Is there a better way?

Answer 1

It looks like it can be done in O (n) time.

• Calculate the amount S. The ideal sum of a subsequence is the longest that is closest to S/2.
• Start with i=j=0and increase jas long as sum(a_i..a_j), and sum(a_i..a_{j+1})will not be as close as possible to the S / 2. Note that it’s ever closer and keep the values i_best,j_best,sum_best.
• i, j , sum(a_i..a_j) sum(a_i..a_{j+1}) S/2. , - i_best,j_best,sum_best, . .

, i j , O (n) . , O (n) .

Answer 2

.

• A subsequence . Haivng , , , , , Partition, , , NP-. , O (Sn), "n" - , "S" - . , "S" .
• , . . "S" . . , , a [i] + a [i + 1] +... + a [j] > S/2. = + 1. , , j.

O (n).

Python:

    from math import fabs
    a = [1, 2, 3, 4, 5]
    i = 0
    j = 0
    S = sum(a)
    s = 0
    while s + a[j] <= S / 2:
        s = s + a[j]    
        j = j + 1
    s = s + a[j]


    best_case = (i, j)
    best_difference = fabs(S / 2 - s)
    while True:    
        if fabs(S / 2 - s) < best_difference:
            best_case = (i, j)
            best_difference = fabs(S / 2 - s)
        if s > S / 2:
            s -= a[i]
            i += 1        
        else:
            j += 1
            if j == len(a):
                break
            s += a[j]

    print best_case
    i = best_case[0]
    j = best_case[1]
    print "Best subarray = ", a[i:j + 1]
    print "Best sum = " , sum(a[i:j + 1])