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

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))