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

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

Этот код помогает найти максимальную сумму любого подмассива, но мне нужно найти, какая максимальная сумма подмассива ›будет, если мне придется удалить в нем самый большой элемент.

Например,
Если у нас есть 7 элементов в массиве как [0, -11,5,5, -10,0,50], максимальная сумма подмассива, если нам нужно удалить его самый большой элемент ‘будет 5
Для 5 элементов [-2,10, -2,10,6] ответ будет 14 < / strong>
Что мне здесь делать?

Похоже на проблему конкуренции — не могли бы вы дать ссылку на источник? Также насколько быстро приемлемо?   —  person keancodeup    schedule 09.05.2021

См. также:  Добавление метки внутри метки на PyQt5
Понравилась статья? Поделиться с друзьями:
IT Шеф
Комментарии: 3
  1. keancodeup

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

     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

  2. keancodeup
    • измените вашу функцию maxSub (), чтобы она возвращала начальный и конечный индексы вашего максимального подмассива.
    • затем возьмите max () этого подмассива и вычтите его из максимума подмассива

    Вот код. max_finder() возвращает максимальную сумму, начальный и конечный индексы. Я реализовал его, следуя Kadane's Algorithm описанному здесь

    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
    
    • а потом
    max_sum, start, end = max_finder(a)
    max_val = max(a[start: end+1])
    print(max_sum - max_val)
    

    Это не удается в таких случаях, как [5, -100, 1, 1], потому что его заманивает большая пятерка, которая затем исчезает. person keancodeup; 09.05.2021

    Да, мне кажется, правильно, я понимаю, о чем говорит @j_random_hacker. заботиться о разработке? person keancodeup; 09.05.2021

    Извините, попробуйте вместо этого [1, 1, -100, 5]. (В вашем max_finder() есть ошибка: max_finder([5, -100, 1, 1]) должно быть (5, 0, 0), но он неправильно возвращает (2, 2, 3). В примерах входных данных, которые я дал обоим, есть подмассивы с суммой 5.) person keancodeup; 10.05.2021

    мои извинения @j_random_hacker, это было неверно при первом вводе, и я не заметил. Я соответствующим образом отредактирую функцию. Спасибо. person keancodeup; 10.05.2021

    Нет проблем, но более серьезная проблема заключается в том, что теперь, когда max_finder() правильно находит интервал максимальной суммы, оба моих примеров ввода дают окончательный ответ 0, когда правильный ответ равен 1. person keancodeup; 10.05.2021

    Возьмем пример [5, -100, 1, 1]. Максимальный интервал составляет [0: 1], то есть только первый индекс. тогда, когда мы вычитаем максимальное значение в пределах этого интервала из максимальной суммы, становится понятно, почему мой ответ равен 0. Можете ли вы объяснить, почему правильным ответом будет 1? ты person keancodeup; 10.05.2021

    Вопрос заключается в том, чтобы указать максимальное значение, которое можно получить, взяв все элементы в интервале, удалив самый большой и просуммировав остальные. Если вы возьмете интервал [1, 1] и удалите самый большой элемент (один из 1s) и просуммируете остальные, вы получите 1. person keancodeup; 10.05.2021

    Давайте продолжим это обсуждение в чате. person keancodeup; 10.05.2021

  3. keancodeup

    Вот повторение, которое кажется довольно быстрым для случайных данных, но более медленным с сильно отсортированными данными). С 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
    
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: