How do I find the maximum sum of subarray if i have to delete the largest element in the subarray

Question

def maxsub(a,N):
    max_so_far = a[0]
    curr_max = a[0]

    for i in range(1,N):
        curr_max = max(a[i], curr_max + a[i])
        max_so_far = max(max_so_far,curr_max)
    return max_so_far


N = int(input())
arr = [int(input()) for _ in range(N)]

if all(x > 0 for x in arr) == True:
    print(sum(arr) - max(arr))
else:
    print(maxsub(arr,N))

This code helps in finding maximum sum of any subarray, but I need to find what maximum sum of subarray >will be if I have to delete the largest element in it.

For e.g.
If we have 7 elements in an array as [0,-11,5,5,-10,0,50] the 'maximum sum of subarray if we have to delete its largest element' will be 5
For 5 elements [-2,10,-2,10,6] the answer will be 14
What will I have to do here ?

Answer 1

Here is a recurrence that seems to be pretty fast for random data but slower with largely sorted data). With 3000 elements, it seems about 10-20 times faster than Amo Robb's maxsub3 function (for random, not sorted data). The repl includes accuracy tests against brute force as well. The recurrence is naive - some of the backwards runs could have the best solution looked up based on the max_subarray threshold.

Let f(i, is_max, subarray_max) represent the largest sum ending at the ith element, where is_max indicates if the element is the maximum, and subarray_max is the maximum of the subarray. Then:

# max isn't used if the element 
# ending the subarray is fixed
# as the maximum.
def f(A, i, is_max, subarray_max, memo, ps, pfxs):
  key = str((i, is_max, subarray_max))

  if key in memo:
    return memo[key]

  if is_max:
    if i == 0 or A[i-1] > A[i]:
      return 0

    result = f(A, i - 1, False, A[i], memo, ps, pfxs)
    memo[key] = result

    return result
  
  # not is_max
  if i == 0:
    if A[i] > subarray_max:
      return 0
    return max(0, A[i])

  # If max is not defined,
  # we MUST include all previous
  # elements until the previous equal or
  # higher element. If there is no
  # previous equal or higher element,
  # return -Infinity because a subarray
  # ending at A[i] cannot correspond
  # with false is_max.
  if subarray_max == None:
    prev = ps[i]
    if prev == -1:
      return -float('inf')

    best = -float('inf')
    temp = ps[i]

    while ps[temp] != -1:
      candidate = pfxs[i] - pfxs[temp] + f(A, temp, True, None, memo, ps, pfxs)

      if candidate > best:
        best = candidate
        # The prev equal or higher could still
        # be smaller to another.
      candidate = pfxs[i] - pfxs[temp] + f(A, temp, False, None, memo, ps, pfxs)
      if candidate > best:
        best = candidate

      temp = ps[temp]

    candidate = pfxs[i] - pfxs[temp] + f(A, temp, True, None, memo, ps, pfxs)

    if candidate > best:
        best = candidate

    memo[key] = best

    return best
  
  # If max is defined, the previous
  # equal or higher could be higher
  # than max, in which case we need
  # not include all elements in between.
  if A[i] > subarray_max:
    return 0

  result = max(0, A[i] + f(A, i - 1, False, subarray_max, memo, ps, pfxs))

  memo[key] = result

  return result

def g(A):
  memo = {}
  best = -float('inf')

  ps = find_prev_greater_elements(A)

  pfxs = [A[0]] + [None] * len(A)
  for i in range(1, len(A)):
    pfxs[i] = A[i] + pfxs[i-1]

  for i in range(len(A)):
    best = max(best, f(A, i, True, None, memo, ps, pfxs))
    if i > 0:
      best = max(best, f(A, i, False, None, memo, ps, pfxs))

  return best


# Adapted from https://stackoverflow.com/a/9495815/2034787
def find_prev_greater_elements(xs):
  ys=[-1 for x in xs]
  stack=[]
  for i in range(len(xs)-1, -1, -1):
    while len(stack)>0 and xs[i] >= xs[stack[-1]]:
      ys[stack.pop()]=i
    stack.append(i)
  return ys

Answer 2

Another approach could be:

 def maxsub(a,N):
    bestSumsWithoutMax=sys.float_info.min
    bestSum=0
    for i in range(len(a)-1):
        LastInd = min(len(a)+1,i+N+1)
        for j in range(i+2,LastInd):
            subA = a[i:j]
            subSum =sum(subA)
            subSumWM =subSum-max(subA)
            if(bestSumsWithoutMax<subSumWM):
                bestSumsWithoutMax=subSumWM
                bestSum = subSum
    return bestSumsWithoutMax, bestSum

  sumsWithoutMax, associatedSum=  maxsub(a,N)
  print("%f  %f" % (associatedSum, sumsWithoutMax))

Beware that the performance of this algorithm could be different from the one resulting from a more explicit indexing, in case you are dealing with large arrays.

The code above can be condensed to:

 def maxsub2(a,N):
    bestSumWMAndIndex = max([(sum(a[i:j])- max(a[i:j]),i,j) for i in range(len(a)-1) for j in range(i+2,min(len(a)+1,i+N+1))])
    return bestSumWMAndIndex[0], sum(a[bestSumWMAndIndex[1]:bestSumWMAndIndex[2]])

 sumsWithoutMax, associatedSum=   maxsub2(a,N)

 print("%f  %f" % (associatedSum, sumsWithoutMax))

EDIT -----------------------------------

if performance is key, first consider programming it in another language. If you have to stick to Python, you can try:

  def maxsub3(a,N):
    bestSumsWithoutMax=sys.float_info.min
    bestSum=0    
    for i in range(len(a)-1):
        LastInd = min(len(a),i+N)
        subAini = a[i:i+2]
        subSum =sum(subAini)
        maxA = max(subAini)
        subSumWM =subSum-maxA
        if(bestSumsWithoutMax<subSumWM):
            bestSumsWithoutMax=subSumWM
            bestSum = subSum
        for j in range(i+2,LastInd):
            A = a[j]
            subSum+=A
            if(A>maxA):                
                subSumWM+=maxA
                maxA=A
            else:
                subSumWM+=A

            if(bestSumsWithoutMax<subSumWM):
                bestSumsWithoutMax=subSumWM
                bestSum = subSum

    return bestSumsWithoutMax, bestSum

sumsWithoutMax, bestSum=   maxsub(b,N)
print("%f  %f" % (bestSum, sumsWithoutMax))

Answer 3

• modify your maxSub() function to return the start and end indices of your max subarray.
• then take the max() of that subarray, and subtract it from the subarray's maximum

Here's some code. max_finder() returns the max sum, start, end indices. I implemented it following Kadane's Algorithm described here

def max_finder(a):
    cur_max, cur_start, cur_end = a[0], 0, 0
    max_so_far, start_so_far, end_so_far = a[0], 0, 0
    for i in range(1, len(a)):
        if a[i] > cur_max+a[i]:
            cur_max, cur_start, cur_end = a[i], i, i
        else:
            cur_max, cur_end = cur_max + a[i], i
        if (cur_max - max(a[cur_start: cur_end+1])) > (max_so_far - max(a[start_so_far: end_so_far+1])):
            max_so_far, start_so_far, end_so_far = cur_max, cur_start, cur_end
    return max_so_far, start_so_far, end_so_far

• and then

max_sum, start, end = max_finder(a)
max_val = max(a[start: end+1])
print(max_sum - max_val)