Python: максимальная сумма подмассива

Я только что попытался начать изучать Python сегодня, поэтому я не разбираюсь в его функциях. Однако я обнаружил проблему с максимальным подмассивом и хотел попытаться решить ее с помощью нескольких простых логических команд, которые есть в моем распоряжении. Я застрял, и почти уверен, что проблема в моей логике, а не в синтаксисе, хотя я вполне могу ошибаться. Вот мой код до сих пор...

def maxSequence(arr): #Latest attempt, some issue.
  old_arr = []
  print(arr)
  while old_arr != arr:
    old_arr = arr
    if arr[0] > 0 and arr[len(arr)-1] > 0: #For when both sides are positive, need to be sure there is not anything to be gained by eliminating some side section
      new_sum = 0
      y=0
      while new_sum >= 0 and y != -1:
        new_sum = sum(arr[:y])
        y=y+1
        if y == len(arr)-1:
          y=-1
      if y != -1:
        arr = arr[y-1:]
      print("left %s" %(new_sum))
      print("left %s" % (arr))
      new_sum = 0
      y = 0
      while new_sum >= 0 and y != -1:
        new_sum=sum(arr[(len(arr)-y):])
        y=y+1
        if y == len(arr)-1:
          y=-1
      if y != -1:
        arr = arr[:len(arr)-y+1]
      print("right %s" %(new_sum))
      print("right %s" % (arr))
    else:
      while arr[0] < 0 or arr[len(arr)-1] < 0: #To eliminate negatives on sides
        if arr[0] < 0:
         arr = arr[1:]
        if arr[len(arr)-1] < 0:
         arr = arr[:len(arr)-1]
        print("negative %s" % (arr))
  print(arr)
  print(sum(arr))

Различные функции печати показывают каждое решение, принятое программой, и помогают мне визуализировать то, что происходит во время выполнения циклов.

Это не дает правильный результат 105 при задании списка

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]

Он заканчивается суммой 94, сократив список до

[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]

Извините за длинный пост, но я просто не могу понять, что я делаю неправильно. Спасибо за вашу помощь заранее!

Вот результат, когда вышеупомянутый список дан в качестве входных данных, я прошел и просмотрел каждый шаг, и каждое исключение из списка кажется мне логичным, я не знаю, как можно получить конечную сумму 105. Если кто-нибудь может помочь мне понять, я был бы очень признателен!

[26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, 
-27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, 
-25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17, -26]
negative [26, -25, -23, -2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, 
-8, -25, -27, 15, -29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 
11, 6, -10, -25, 27, -18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
left -22
left [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4, -25, 17]
right -8
right [-2, 3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9, -4]
negative [3, -6, -5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, 
-29, -11, -12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25, -22, 8, 9]
left -3
left [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25, -22, 8, 9]
right -5
right [-5, 15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25]
negative [15, 7, 8, 17, 15, 29, -2, 16, -25, -8, -25, -27, 15, -29, -11, 
-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6, 
-13, -13, 25]
left -5
left [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6, -13, -13, 25]
right -1
right [-12, 1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, 
-18, 6]
negative [1, -14, 21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 
6]
left -13
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27, -18, 6]
right -12
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
left 84
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6, -10, -25, 27]
right -8
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
left 77
left [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
right 53
right [21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
[21, 20, 30, -29, 17, 9, -19, 28, 11, 6]
94

python sum logic maximize sub-array
person Community    schedule 22.07.2017    source источник
comment
Не могли бы вы дать краткое описание проблемы, которую вы пытаетесь решить? Не глядя на ваш код, похоже, вы пытаетесь получить максимальный подсписок списка (то есть смежные элементы). Есть ли другие ограничения? (длина и т.д.)   -  person Patrick Haugh    schedule 22.07.2017
comment
Это правильно, нет никаких ограничений, кроме того, что он должен быть подсписком списка, который имеет максимальную сумму из всех возможных подсписков.   -  person    schedule 22.07.2017
comment
Не причина вашей текущей проблемы, но вы, похоже, неправильно обрабатываете нули на входе.   -  person user2357112 supports Monica    schedule 22.07.2017
comment
Вот более похожее на Python решение max((l[start:end] for start in range(len(l)) for end in range(start+1, len(l)+1)), key=sum)   -  person Patrick Haugh    schedule 22.07.2017
comment
Это определенно не самый эффективный способ решить эту проблему.   -  person Patrick Haugh    schedule 22.07.2017

Ответы (3)


arrow_upward
2
arrow_downward

Я продемонстрирую, что не так с вашим алгоритмом, на небольшом примере.

Скажем, вход

[2, -3, 1]

[2] явно является максимальным подмассивом. Однако ваш алгоритм будет смотреть на эту часть:

[2, -3, 1]
 ^^^^^

и увидеть, что он может увеличить сумму массива, удалив [2, -3].

Удаление отрицательных подмассивов с концов приводит к неправильному результату, если максимальный подмассив является частью отрицательного подмассива. Вам понадобится более умный алгоритм.

person user2357112 supports Monica    schedule 22.07.2017
comment
Благодарю вас! Это определенно так! - person ; 22.07.2017

arrow_upward
0
arrow_downward

Почему бы просто не использовать алгоритм Кадане, который занимает O(n) времени??

Алгоритм Кадане (DP):

Initialize:
    max_so_far = 0
    max_ending_here = 0

Loop for each element of the array
  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_ending_here < 0)
            max_ending_here = 0
  (c) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far
person SrGrace    schedule 22.07.2017
comment
Я не исследовал проблему, прежде чем пытаться понять ее, я был уверен, что она решена, но просто хотел попытаться понять ее. Я обязательно посмотрю на это решение, хотя! - person ; 22.07.2017
comment
Это наиболее эффективное решение для подобных проблем. - person SrGrace; 22.07.2017
comment
@MarkM: Это псевдокод, разве ты не знаешь? Я думал, что с репутацией более 3500 вы должны быть достаточно мудры, чтобы понять это: p - person SrGrace; 22.07.2017

arrow_upward
0
arrow_downward

попробуйте этот код. Это работает с временной сложностью O (n), потому что он просто запускается n раз.

def manSubArraySum(a):
    currentbest = 0
    overallbest = a[0]
    for p in a: # [1,2,-2,4]
        currentbest = currentbest+p # first step cb = -10
        if currentbest> overallbest: # !true
            overallbest = currentbest
        if currentbest<0: # nottrue
            currentbest =0 # 0

    return overallbest
person Bikash Cocboy    schedule 30.06.2021