Невозможно реализовать эту программу python, чтобы найти сумму подмассива с максимальной суммой двумерного массива

Question

Want To: Возвращать сумму подмассива максимальной суммы 2D-массива

В следующей программе я сначала вычисляю сумму подмассива максимальной суммы, граничные столбцы которой L и R, где L начинается с 0 to (cols-1) и R выполняется от L до (cols-1), cols - это количество столбцов, а row - это количество строк. Тогда ясно, что требуемый ответ является максимальным из всех этих значений. Я также обновляю максимальную сумму, максимум, вместе.

См. Здесь известный алгоритм

Моя функция max_sum_of_subarray_in_1D_array (A, n) возвращает сумму максимального подмассива массива 1D за время O (N), и эта функция работает отлично.

def max_sum_of_subarray_in_1D_array(A, n):
    for i in range(1, n):
        A[i] = max(A[i], A[i]+A[i-1])
    iMax = 0
    for i in range(1, n):
        if A[i] > A[iMax]:
            iMax = i

    return A[iMax]


def max_sum_of_subarray_in_2D_array(A, rows, cols):
    temp = []
    max = -1000000

    for L in range(0, cols):
        for i in range(0, rows):
            temp.append(0)
        for R in range(L, cols):
            for i in range(0, rows):
                temp[i] += A[i][R]
            val = max_sum_of_subarray_in_1D_array(temp, rows);
            if val > max:
                max = val

    return max


A = [[1, 2, -1, -4, -20],
    [-8, -3, 4, 2, 1],
    [3, 8, 10, 1, 3],
    [-4, -1, 1, 7, -6]]

print(max_sum_of_subarray_in_2D_array(A, 4, 5))

Однако я получаю неправильный вывод 1024

Правильный вывод: 29

Может кто-нибудь указать, где я делаю неправильно. Я оглядывался снова и снова, не могу найти ошибку.

Answer 1

в основном у вас было две проблемы в вашем коде: -

1. Ваш метод max_sum_of_subarray_in_1D_array() не работает должным образом.
2. Внутри for L in range(0, cols): l oop вам нужно переназначить temp = [], в противном случае вы будете продолжать добавлять значения, и сумма будет увеличиваться, что приведет к неправильным выводам.

Я публикую обновленный код, см. его.

def max_sum_of_subarray_in_1D_array(a, size): 
  max_so_far = -1000000
  max_ending_here = 0

  for i in range(0, size): 
    max_ending_here = max_ending_here + a[i] 
    if (max_so_far < max_ending_here): 
      max_so_far = max_ending_here 

    if max_ending_here < 0: 
      max_ending_here = 0   
  return max_so_far 


def max_sum_of_subarray_in_2D_array(A, rows, cols):
  temp = []
  maxValue = -1000000

  for L in range(0, cols):
    temp = []
    for i in range(0, rows):
      temp.append(0)
    for R in range(L, cols):
      for i in range(0, rows):
        temp[i] += A[i][R]
      val = max_sum_of_subarray_in_1D_array(temp, rows)
      if val > maxValue:
        maxValue = val

  return maxValue


A = [[1, 2, -1, -4, -20],
  [-8, -3, 4, 2, 1],
  [3, 8, 10, 1, 3],
  [-4, -1, 1, 7, -6]]

print(max_sum_of_subarray_in_2D_array(A, 4, 5))

Надеюсь, это поможет!