Задача на поиск максимальной суммы подмассива (5 kyu)

Question

вот условия:

Задача о максимальной сумме подмассива состоит в нахождении максимальной суммы непрерывной подпоследовательности в массиве или списке целых чисел:

max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
should be 6: [4, -1, 2, 1]

Простой случай — это когда список состоит только из положительных чисел, а максимальная сумма — это сумма всего массива. Если список состоит только из отрицательных чисел, вместо этого верните 0.

Пустой список считается имеющим нулевую наибольшую сумму. Обратите внимание, что пустой список или массив также является допустимым подсписком/подмассивом.

вот мой код:

def max_sequence(arr):
    if len(arr) == 0:
        return 0
    else:
        max_num = arr[0]
        c1, c2 = 0, 0
        for i in range(len(arr)):
            for j in range(len(arr)):
                if sum(arr[c1:c2]) > max_num:
                    max_num = sum(arr[c1:c2])
                c1 += 1
                c2 += 1
            c1 = 0
            c2 = i
    return max_num

решение с использованием алгоритма Kadane's Algorithm:

def max_sequence(arr):
    if len(arr) == 0:
        return 0
    else:
        maxim = 0
        maxim2 = 0
        for i in (arr):
            maxim = maxim + i
            maxim = max(maxim, 0)
            maxim2 = max(maxim, maxim2)
    return maxim2

так как на валидатор с codewars не пускает мое 1е решение из 59 случаев 1 случай оказывается не верным и узнать на чем проваливается тест не предоставляеться возможным. Где ошибка в моей 1й реализации?

Answer 1

разобрался на другом примере:

Временная сложность: O(N), где N — размер массива.

    def maximumSubarraySum(arr):
       n = len(arr)
       maxSum = -1e8
       currSum = 0

       for i in range(0, n):
           currSum = currSum + arr[i]
           if(currSum > maxSum):
               maxSum = currSum
           if(currSum < 0):
               currSum = 0
      
       return maxSum

    if __name__ == "__main__":
    # Your code goes here
    print(maximumSubarraySum([1, 3, 8, -2, 6, -8, 5]))

БЛОГ НА HUSL

Задача на поиск максимальной суммы подмассива (5 kyu)

Ответы (1 шт):