python - 如果我必须删除子数组中的最大元素，如何找到子数组的最大和

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.

例如
如果我们在数组中有 7 个元素为 [0,-11,5,5,-10,0,50] “如果我们必须删除其最大元素，子数组的最大和”将是 5
对于 5 个元素 [-2,10,-2​​,10,6] 答案是 14
我要在这里做什么？

Answer 1

另一种方法可能是:

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

请注意，如果您正在处理大型数组，则此算法的性能可能与更显式索引产生的性能不同。
上面的代码可以压缩为:

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

编辑-----------------------------------
如果性能是关键，首先考虑用另一种语言编程。如果你必须坚持使用 Python，你可以尝试:

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