Подписей с максимальной суммой?

Question

Я смущаюсь с этим вопросом в том, что он пытается спросить.

Запись функции mssl() (минимальная сумма Подсписок), которая принимает в качестве входных данных список целых чисел. Затем он вычисляет и возвращает сумму максимальной суммы подписок списка входных данных. Подсчет максимальной суммы представляет собой подсписку (срез) входного списка, сумма записей которого наибольшая. Пустой подсчет определяется как сумма 0. Например, подвычислитель максимальной суммы из списка [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] составляет [5, -2, 7, 7, 2] , а сумма его записей - 19.

Если бы я должен был использовать эту функцию, она должна вернуть что-то похожее на

>>> l = [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] 
>>> mssl(l) 
19 
>>> mssl([3,4,5]) 
12 
>>> mssl([-2,-3,-5]) 
0 

Как я могу это сделать?

Вот мой текущий попробовать, но это не дает ожидаемого результата:

def mssl(x): 
    ' list ==> int ' 
    res = 0 
    for a in x: 
     if a >= 0: 
      res = sum(x) 
     return res 
    else: 
     return 0 

Answer 1

Он просит вас выбрать меньший подраздел списка таким образом, что сумма мень- Подсекция является самым большим.

Если список все положительный [1 2 3] тогда, конечно, подраздел с наибольшей суммой является только суммой всего списка [1 2 3] которое 6.

Если список весь отрицательный [-1 -2 -3] то подраздела с самым большим сумма ничего [], который имеет сумму 0.

Однако, если в списке есть некоторые положительные и некоторые негативные решения труднее

[1 2 3 -100 3 4 5] вы должны увидеть [3 4 5] и вернуть 12

[1 2 3 -2 3 4 5] вы должны использовать все это и вернуть 16

Answer 2

Так что, если вы понимаете, что подсписок является (или кусочек, который можно считать то же самое), срез определяется индексом начальной и конечный индекс.

Так что, возможно, вы можете попробовать и перебрать все возможные начальные и конечные индексы и вычислить соответствующую сумму, а затем вернуть максимальную.

Подсказка: начальный индекс может варьироваться от 0 до len(given_list)-1. Конечный индекс может быть от start_index до len(given_list)-1. Вы можете использовать вложенный цикл for для проверки всех возможных комбинаций.

Answer 3

Простым решением является перебор по списку и просто попробуйте добавить кусочки, пока не найдете лучший. Здесь я также включил возможность вернуть фактический подсписк, по умолчанию это False. Я использовал defaultdict для этой цели, потому что это проще, чем поиск.

from collections import defaultdict 

def mssl(lst, return_sublist=False): 
    d = defaultdict(list) 
    for i in range(len(lst)+1): 
     for j in range(len(lst)+1): 
      d[sum(lst[i:j])].append(lst[i:j]) 
    key = max(d.keys()) 
    if return_sublist: 
     return (key, d[key]) 
    return key 

print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 
19 
print mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5], True) 
(19, [[5, -2, 7, 7, 2]]) 

Bonus: Список метод понимания:

def _mssl(lst): 
    return max(sum(lst[i:j]) for i in xrange(len(lst)+1) for j in xrange(i, len(lst)+1)) 

Answer 4

Это различие, вероятно, не важно ОР, который, кажется, просто пытаюсь понять, как решить эту проблему вообще, но я думал, Стоит отметить:

Другие решения здесь включают в себя повторное суммирование всех подчастей списка. Мы можем избежать этих повторяющихся сумм, используя динамическое программирование, так как, конечно, если мы уже знаем сумму от i до j, нам не нужно добавлять их снова, чтобы получить сумму от i до j+1!

То есть, сделайте 2d массив частичных сумм, так что partsum[i, j] == sum(lst[i:j]). Нечто подобное (с использованием словаря, потому что легче индексировать с; NumPy массив будет одинаково легко и более эффективно):

import operator 

def mssl(lst, return_sublist=False): 
    partsum = { (0, 0): 0 } # to correctly get empty list if all are negative 
    for i in xrange(len(lst) - 1): # or range() in python 3 
     last = partsum[i, i+1] = lst[i] 
     for j in xrange(i+1, len(lst)): 
      last = partsum[i, j+1] = last + lst[j] 

    if return_sublist: 
     (i, j), sum = max(partsum.iteritems(), key=operator.itemgetter(1)) 
     return sum, lst[i:j] 

    return max(partsum.itervalues()) # or viewvalues() in 2.7/values() in 3.x 

Это занимает O (N^2) время и память, в отличие от O (п^3) время и память O (1) для подхода Лев/Инбар (если не реализовывать его так же, как пример первого примера Inbar).

Answer 5

На самом деле очень элегантное, очень эффективное решение с использованием динамического программирования. O (1) пробел и O (n) время - этого нельзя бить!

Определить A быть входным массивом (нуль-индексированный) и B[i] быть максимальной суммой по всем подспискам заканчивающихся, но не включая позицию i (т.е. все подсписки A[j:i]). Поэтому B[0] = 0 и B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0) и так далее. Тогда, очевидно, решение дается просто max(B[0], ..., B[n]).

Поскольку каждое B значение зависит только от предыдущего B, мы можем избежать хранения всего B массив, таким образом давая нам наше O (1) пространство гарантии.

При таком подходе mssl сводится к очень простой цикл:

def mssl(l): 
    best = cur = 0 
    for i in l: 
     cur = max(cur + i, 0) 
     best = max(best, cur) 
    return best 

Демонстрация:

>>> mssl([3,4,5]) 
12 
>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 
19 
>>> mssl([-2,-3,-5]) 
0 

---

Если вы хотите, начальный и конечный срез показателей, тоже нужно отслеживать еще несколько бит информации (обратите внимание, что это все еще O (1) пробел и время O (n), это немного больнее):

def mssl(l): 
    best = cur = 0 
    curi = starti = besti = 0 
    for ind, i in enumerate(l): 
     if cur+i > 0: 
      cur += i 
     else: # reset start position 
      cur, curi = 0, ind+1 

     if cur > best: 
      starti, besti, best = curi, ind+1, cur 
    return starti, besti, best 

Это возвращает кортеж (a, b, c) таким образом, что sum(l[a:b]) == c и c максимальна:

>>> mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 
(3, 8, 19) 
>>> sum([4, -2, -8, 5, -2, 7, 7, 2, -6, 5][3:8]) 
19 

Answer 6

Это the maximum sub-array problem.Алгоритм Kadane может решить в O(n) времени и O(1) пространстве, и это происходит следующим образом:

def mssl(x): 
    max_ending_here = max_so_far = 0 
    for a in x: 
     max_ending_here = max(0, max_ending_here + a) 
     max_so_far = max(max_so_far, max_ending_here) 
    return max_so_far 

Answer 7

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

Реализация Java на этот вопрос:

public static int maximumSumSubSequence(int[] array) { 

    if (null == array) { 
     return -1; 
    } 

    int maxSum = Integer.MIN_VALUE; 
    int startIndexFinal = 0; 
    int endIndexFinal = 0; 
    int currentSum = 0; 
    int startIndexCurrent = 0; 

    for (int i = 0; i < array.length; i++) { 
     currentSum += array[i]; 

     if (currentSum > maxSum) { 
      maxSum = currentSum; 
      endIndexFinal = i; 
      startIndexFinal = startIndexCurrent; 
     } 
     if (currentSum <= 0) { 
      currentSum = 0; 
      startIndexCurrent = i + 1; 
     } 
    } 
    System.out.println("startIndex: " + startIndexFinal + " endIndex: " + endIndexFinal); 
    return maxSum; 
} 

Answer 8

Вот реализация в Java, используя алгоритм Kadane, которая печатает индексы самой большой суммы. Реализация занимает время O (n) и O (1).

public static void maxSumIndexes(int[] a) { 

    int size = a.length; 
    if(size == 0) return; 

    int maxAtIndex = a[0], max = a[0]; 
    int bAtIndex = 0; 
    int b = 0, e = 0; 

    for(int i = 1; i < size; i++) { 
     maxAtIndex = Math.max(a[i], a[i] + maxAtIndex); 
     if(maxAtIndex == a[i]) 
      bAtIndex = i; 

     max = Math.max(max, maxAtIndex); 
     if(max == maxAtIndex) { 
      e = i; 
      b = (b != bAtIndex)? bAtIndex : b; 
     } 
    } 

    System.out.println(b); 
    System.out.println(e); 
} 

Answer 9

Это post представляет три способа найти максимальный подмассив массива.

• Грубая сила (О (п * п))
• Разделяй и властвуй (O (nlgn))
• алгоритм Kadane (в О (п))

Среди них, самый быстрый один - алгоритм Кадане, имеющий временную сложность O (n).

Answer 10

если кто-то ищет более длинную версию коды, здесь:

def mesl(lst): 
    sub_sum = list() 
    row_sum = list() 
    for i in range(len(lst)): 
     sub_sum = list() 
     sub_sum.append(lst[i]) 
     k = 1 
     for j in range(i+1,len(lst)): 
      sub_sum.append(sub_sum[k-1] + lst[j]) 
      k+=1 
     row_sum.append(max(sub_sum))  
    sum = max(row_sum) 
    if sum < 0: 
     sum = 0 
    return sum 

Answer 11

по вопросу, в случае, если все элементы в списке отрицательны, он должен вернуть максимальную сумму как «НОЛЬ»

вместо этого, если вы хотите, чтобы вывод, как максимум подмассива (в отрицательном числе), то ниже код поможет:

In [21]: def mssl(l): 
...:  best = cur = l[0] 
...:  for i in range(len(l)): 
...:   cur = max(cur + l[i], l[i]) 
...:   best = max(best, cur) 
...:  return best 

примеров:

In [23]: mssl([-6, -44, -5, -4, -9, -11, -3, -99]) 
Out[23]: -3 
In [24]: mssl([-51, -23, -8, -2, -6]) 
Out[24]: -2 

для положительных и отрицательных чисел

In [30]: mssl([4, -2, -8, 5, -2, 7, 7, 2, -6, 5]) 
Out[30]: 19