Как найти максимальную сумму подмассива, если мне нужно удалить самый большой элемент в подмассиве

Другой подход мог бы быть:

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

Что такое N и зачем он нужен? — person keancodeup; 10.05.2021

N — максимальный размер подмассива. Я не знаю, зачем это нужно, но он был использован в вопросе, поэтому я просто сохранил это требование. — person keancodeup; 10.05.2021

maxsub3([-10, 7, -4, 1, 5], 5), похоже, возвращает (1, 8). Я думаю, что правильный результат будет (2, 9). — person keancodeup; 10.05.2021

Простите, вы правы. Это должно быть for j in range(i+2,LastInd):. Исправляю свой ответ — person keancodeup; 11.05.2021

Вот повторение, которое кажется довольно быстрым для случайных данных, но более медленным с сильно отсортированными данными). С 3000 элементов это кажется примерно в 10-20 раз быстрее, чем maxsub3 (для случайных, не отсортированных данных). Ответ также включает тесты точности против грубой силы. Повторение наивно — некоторые из обратных прогонов могли найти лучшее решение на основе порогового значения max_subarray.

Пусть f(i, is_max, subarray_max) представляет наибольшую сумму, заканчивающуюся на i-м элементе, где is_max указывает, является ли элемент максимальным, а subarray_max — максимумом подмассива. Потом:

# 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