Поиск максимального неотрицательного подмассива в python

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

Ниже функция имеет параметр в качестве входа a, и необходимо вернуть вывод. Подмассивов может быть несколько, так как их максимальная сумма может быть равна. Код, похоже, не работал должным образом.

def max_sum_subarray(a):
        N, sub_sum, max_sum, subArrays = len(a), 0, 0, {}
        p,q=0,0    #starting and ending indices of a max sub arr

        for i in range(N):
            q=i
            sub_sum+=a[i]

            if(a[i]<0):
                q-=1
                if(sub_sum>=max_sum):
                    if(sub_sum>max_sum):
                        subArrays.clear()
                        subArrays[sub_sum]=[(p,q)]
                    else:
                        subArrays[sub_sum].append((p,q))

                sub_sum=0
                p=i+1

        if(sub_sum>=max_sum):
            if(sub_sum>max_sum):
                subArrays.clear()
                subArrays[sub_sum]=[(p,q)]
            else:
                subArrays[sub_sum].append((p,q))
        return(subArrays[p:q+1])


Когда я пытался выполнить ввод

a=[ 1, 2, 5, -7, 2, 5 ]

Ожидаемый результат - [1, 2, 5], но вместо этого он дал [2, 5]. Может ли кто-нибудь опубликовать решение в python?


python sub-array
person Krishnavamshi Chintala    schedule 14.07.2019    source источник
comment
Не могли бы вы объяснить алгоритм, который вы реализовали?   -  person Nir Alfasi    schedule 14.07.2019
comment
subArrays - это dict, при запуске вашего кода я получаю TypeError: unhashable type: 'slice' в строке return...   -  person Adam.Er8    schedule 14.07.2019
comment
Подход: начните с первого индекса и продолжайте добавлять сумму, пока не найдете отрицательный элемент, с этого момента начните добавлять сумму с нуля, но также сохраняйте максимальные суммы. Здесь я создал ключ обновления словаря как максимальную сумму и значение, поскольку до сих пор требовался начальный и конечный индекс подмассива.   -  person Krishnavamshi Chintala    schedule 14.07.2019

Ответы (2)


arrow_upward
3
arrow_downward

Похоже, вы делаете это сложнее, чем необходимо. Вы можете просто отслеживать максимальный массив, видимый далеко, и текущий массив, в который вы вставляете - вам действительно не нужно заботиться ни о чем другом. Когда вы нажмете отрицательное значение (или конец массива), решите, должен ли текущий быть новым максимумом:

def maxSub(a):
    max_so_far = []
    max_sum = 0
    cur = []
    for n in a:
        if n >= 0:
            cur.append(n)
        else:
            cur_sum = sum(cur)
            if cur_sum > max_sum:
                max_sum = cur_sum
                max_so_far = cur
            cur = []

    return max([max_so_far, cur], key = sum)


a=[ 1, 2, 5, -7, 2, 5 ]

maxSub(a)
# [1, 2, 5]

Конечно, itertools.groupby делает это однострочным:

from itertools import groupby

a=[ 1, 2, 5, -7, 2, 5 ]
max([list(g) for k,g in groupby(a, key=lambda x: x>0) if k == True], key=sum)
person Mark    schedule 14.07.2019
comment
Мне нравится groupby подход. Также вам не нужен список cur, просто запомните первый положительный индекс и перейдите cur_sum = sum(a[firstPositive:n]), производительность будет даже быстрее. - person Radosław Cybulski; 14.07.2019
comment
Да, это хороший совет @RadosławCybulski — спасибо. Никогда не уверен, как сбалансировать ясность концепции и эффективность ответов здесь. - person Mark; 14.07.2019
comment
То же самое и здесь, очевидные вещи для меня не кажутся такими уж очевидными после того, как я это напечатаю. Именно поэтому мне нравится отвечать на SO, так как это заставляет меня переосмысливать все, что я пишу, в контексте читателя. - person Radosław Cybulski; 14.07.2019
comment
Это будет приниматься только от некоторых ТС. для TC [0, 0, -1, 0] ожидаемая операция равна 0 0, и она дает только 0, поэтому для этого используйте концепцию скользящих окон. - person Shantanu Gupta; 03.06.2021
comment
@ShantanuGupta сумма [0, 0] больше суммы [0]? Почему одно предпочтительнее другого? - person Mark; 04.06.2021
comment
Второе условие @mark: если сумма любых двух полос равна, то сравните их длину и верните самую длинную длину. здесь сумма [0, 0] и [0] равна 0, но длина [0, 0] велика, поэтому нужно вернуть [0, 0] - person Shantanu Gupta; 06.06.2021
comment
@ShantanuGupta Может быть, еще слишком рано, но я нигде не вижу этого второго условия в вопросе. Где это сказано? Слова length или longest появляются на этой странице только в вашем комментарии. - person Mark; 06.06.2021
comment
[0, 0, -1, 0] — это один из TC в InterviewBit. - person Shantanu Gupta; 06.06.2021

arrow_upward
0
arrow_downward

Для следующих условий:

ПРИМЕЧАНИЕ 1: Если есть ничья, сравните длину сегмента и возвратного сегмента, который имеет максимальную длину.

ПРИМЕЧАНИЕ 2: Если все еще есть ничья, верните сегмент с минимальным начальным индексом.

Вот мой рабочий код на питоне:

def check(max_arr,curr):
    if sum(curr) > sum(max_arr):
        max_arr = curr
    elif sum(curr) == sum(max_arr):
        if len(curr) > len(max_arr):
            max_arr = curr
        elif len(curr) == len(max_arr):
            if max_arr and (curr[0] > max_arr[0]):
                max_arr = curr
    return max_arr

def maxset(A):
    curr = []
    max_arr = []
    for i in A:
        if i >= 0:
            curr.append(i)
        else:
            max_arr = check(max_arr,curr)
            curr = []
    max_arr = check(max_arr,curr)                    
    return max_arr
person Rahil Sayed    schedule 24.06.2021