Максимальный подсчет суммы?

Ответ 1

На самом деле очень элегантное, очень эффективное решение, использующее динамическое программирование. Он занимает 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

Ответ 2

Это проблема максимального подмассива. Алгоритм Кадане может решить его за время 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

Ответ 3

в соответствии с вопросом, в случае, если все элементы в списке отрицательны, он должен вернуть максимальную сумму как "ZERO"

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

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

Ответ 4

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

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

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

Ответ 5

Здесь реализована реализация на Java, используя алгоритм Каданеса, который печатает индексы самой большой суммы. Реализация принимает 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);
}

Ответ 6

Простым решением является перебор по списку и просто попробуйте добавить кусочки, пока не найдете лучший. Здесь я также включил возможность вернуть фактический подсписк, по умолчанию это 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]])

Бонус: метод понимания списка:

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

Ответ 7

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

Если список положителен [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

Ответ 8

Я предполагаю, что это вопрос, чтобы найти подпоследовательность в массиве, которая дает максимальную сумму. Я столкнулся с этой проблемой при поиске максимальной суммы проблемы 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;
}

Ответ 9

Вот самое короткое и лучшее решение в javascript для решения проблемы максимального подмассива:

var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};

Ответ 10

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

Другие решения здесь включают повторное суммирование всех подчастей списка. Мы можем избежать этих повторяющихся сумм с помощью динамического программирования, так как, конечно, если мы уже знаем сумму от 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 (n ^ 3) и O (1) памяти для подхода Lev/Inbar (если это не реализовано так же, как пример первого кода Inbar).

Ответ 11

В этом post представлены три способа поиска максимального подмассива массива.

• Грубая сила (O (n * n))
• Разделить и победить (O (nlgn))
• Алгоритм Кадане (O (n))

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

Ответ 12

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

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

Ответ 13

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

Чтобы разместить массивы с отрицательными значениями, мы создаем наши переменные с первым элементом массива.

def maxSumSubArr(arr):
    cur_sum = best_sum = arr[0]
    for i in range(1, len(arr)):
        cur_sum = max(arr[i], cur_sum+arr[i])
        best_sum = max(best_sum, cur_sum)
    return best_sum

Время выполнения этого подхода - O (n), а сложность пространства - O (1).

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