How to find the max array from both sides

user_16685119 0
Viewed 212

Given an integer array A, I need to pick B elements from either left or right end of the array A to get maximum sum. If B = 4, then you can pick the first four elements or the last four elements or one from front and three from back etc.

Example input:

A = [5, -2, 3, 1, 2]
B = 3

The correct answer is 8 (by picking 5 from the left, and 1 and 2 from the right).

My code:

def solve(A, B):
    n = len(A)
    # track left most index and right most index i,j
    i = 0
    j = n-1
    Sum = 0
    B2 = B  # B for looping and B2 for reference it
    # Add element from front
    for k in range(B):
        Sum += A[k]
        
    ans = Sum
    # Add element from last
    for _ in range(B2):
       # Remove element from front
       Sum -= A[i]
       # Add element from last
       Sum += A[j]
       ans = max(ans, Sum)

    return ans

But the answer I get is 6.

python
4 Answers

Solution

def max_bookend_sum(x, n):
    bookends = x[-n:] + x[:n]
    return max(sum(bookends[i : i + n]) for i in range(n + 1))

Explanation

Let n = 3 and take x,

>>> x = [4, 9, -7, 4, 0, 4, -9, -8, -6, 9]

Grab the "right" n elements, concatenate with the "left" n:

>>> bookends = x[-n:] + x[:n]
>>> bookends  # last three elements from x, then first three
[-8, -6, 9, 4, 9, -7]

Take "sliding window" groups of n elements:

>>> [bookends[i : i + n] for i in range(n + 1)]
[[-8, -6, 9], [-6, 9, 4], [9, 4, 9], [4, 9, -7]]

Now, instead of producing the sublists sum them instead, and take the max:

>>>  max(sum(bookends[i : i + n]) for i in range(n + 1))
22

For your large array A from the comments:

>>> max(sum(bookends[i : i + n]) for i in range(n + 1))
6253
user_62987120

Solution based on sum of the left and right slices:

Data = [-533, -666, -500, 169, 724, 478, 358, -38, -536, 705, -855, 281, -173, 961, -509, -5, 942, -173, 436, -609,
        -396, 902, -847, -708, -618, 421, -284, 718, 895, 447, 726, -229, 538, 869, 912, 667, -701, 35, 894, -297, 811,
        322, -667, 673, -336, 141, 711, -747, -132, 547, 644, -338, -243, -963, -141, -277, 741, 529, -222, -684,
        35]  # to avoid var shadowing


def solve(A, B):
    m, ln = None, len(A)
    for i in range(B):
        r = -(B-i-1)  # r is right index to slice
        tmp = sum(A[0:i + 1]) + sum(A[r:]) if r < 0 else 0
        m = tmp if m is None else max(m, tmp)
    return m


print(solve(Data, 48))  # 6253
user_150353140

A recursive approach with comments.


def solve(A, B, start_i=0, end_i=None):

    # set end_i to the index of last element
    if end_i is None:
        end_i = len(A) - 1

    # base case 1: we have no more moves
    if B == 0:
        return 0

    # base case 2: array only has two elemens
    if end_i - start_i == 1:
        return max(A)

    # next, we need to choose whether to use one of our moves on 
    # the left side of the array or the right side. We compute both, 
    # then check which one is better. 
    
    # pick the left side to sum
    sum_left = A[start_i] + solve(A, B - 1, start_i + 1, end_i)

    # pick the right side to sum
    sum_right = A[end_i] + solve(A, B - 1, start_i, end_i - 1)

    # return the max of both options
    return max(sum_left, sum_right)

arr = [5, -2, 3, 1, 2]
print(solve(arr, 3)) # prints 8
user_42055470

The idea is if we have this list:

[5, 1, 1, 8, 2, 10, -2]

Then the possible numbers for B=3 would be:

lhs = [5,  1,  1]  # namely L[+0], L[+1], L[+2]
rhs = [2, 10, -2]  # namely R[-3], R[-2], R[-1]

The possible combinations would be:

[5,  1,  1]  # L[+0], L[+1], L[+2]
[5,  1, -2]  # L[+0], L[+1], R[-1]
[5, 10, -2]  # L[+0], R[-2], R[-1]
[2, 10, -2]  # R[-3], R[-2], R[-1]

As you can see, we can easily perform forward and backward iterations which will start from all L (L[+0], L[+1], L[+2]), and then iteratively replacing the last element with an R (R[-1], then R[-2], then R[-3]) up until all are R (R[-3], then R[-2], then R[-1]).

def solve(A, B):
    n = len(A)
    max_sum = None
    for lhs, rhs in zip(range(B, -1, -1), range(0, -(B+1), -1)):
        combined = A[0:lhs] + (A[rhs:] if rhs < 0 else [])
        combined_sum = sum(combined)
        max_sum = combined_sum if max_sum is None else max(max_sum, combined_sum)
    return max_sum

for A in [
    [5, 1, 1, 8, 2, 10, -2],
    [5, 6, 1, 8, 2, 10, -2],
    [5, 6, 3, 8, 2, 10, -2],
]:
    print(A)
    print("\t1 =", solve(A, 1))
    print("\t2 =", solve(A, 2))
    print("\t3 =", solve(A, 3))
    print("\t4 =", solve(A, 4))

Output

[5, 1, 1, 8, 2, 10, -2]
    1 = 5
    2 = 8
    3 = 13
    4 = 18
[5, 6, 1, 8, 2, 10, -2]
    1 = 5
    2 = 11
    3 = 13
    4 = 20
[5, 6, 3, 8, 2, 10, -2]
    1 = 5
    2 = 11
    3 = 14
    4 = 22
user_110438250
Related