ti-enxame.com

Sub-lista de soma máxima?

Estou me confundindo com essa questão com o que ela está tentando perguntar.

Função de gravação mssl() (soma mínima da sub-lista) que recebe como entrada uma lista de inteiros. Em seguida, calcula e retorna a soma da sub-lista de soma máxima da lista de entrada. A sub-lista de soma máxima é uma sub-lista (fatia) da lista de entrada cuja soma de entradas é maior. A sub-lista vazia é definida como a soma 0. Por exemplo, a sub-lista de soma máxima da lista [4, -2, -8, 5, -2, 7, 7, 2, -6, 5] é [5, -2, 7, 7, 2] e a soma de suas entradas é 19.

Se eu fosse usar essa função, deveria retornar algo semelhante a

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

Como eu posso fazer isso?

Aqui está a minha tentativa atual, mas não produz o resultado esperado:

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

Na verdade, existe uma solução muito elegante e muito eficiente usando programação dinâmica . Demora O(1) espaço , e O(n) tempo - isso não pode ser batida!

Defina A para ser a matriz de entrada (zero-indexada) e B[i] a soma máxima sobre todas as sub-listas que terminam em, mas não inclui a posição i (ou seja, todas as sub-listas A[j:i]). Portanto, B[0] = 0 e B[1] = max(B[0]+A[0], 0), B[2] = max(B[1]+A[1], 0), B[3] = max(B[2]+A[2], 0) e assim por diante. Então, claramente, a solução é dada simplesmente por max(B[0], ..., B[n]).

Como todo valor B depende apenas da B anterior, podemos evitar o armazenamento de toda a matriz B, dando-nos nossa garantia de espaço O(1).

Com essa abordagem, mssl reduz a um loop muito simples:

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

Demonstração:

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

Se você quiser os índices de fatia inicial e final, também precisa rastrear mais alguns bits de informação (note que este ainda é O(1) espaço e O(n) tempo é um pouco mais peludo):

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

Isso retorna um Tuple (a, b, c) tal que sum(l[a:b]) == c e c é maximal:

>>> 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
54
nneonneo

Este é o problema máximo de sub-array . O algoritmo de Kadane pode resolvê-lo em O(n) time e O(1) space, e é o seguinte:

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
7
Faraz

de acordo com a pergunta, no caso, se todos os elementos da lista são negativos, deve retornar a soma máxima como 'ZERO'

em vez disso, se você quiser a saída como máximo de subarray (em número negativo), o código abaixo ajudará:

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

exemplos:

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

para números positivos e negativos

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

Então, se você entender o que é uma sub-lista (ou uma fatia, que pode ser considerada a mesma coisa), a fatia é definida pelo índice inicial e pelo índice final.

Então, talvez você possa tentar iterar todos os possíveis índices de início e fim e calcular a soma correspondente, depois retornar o máximo.

Dica: o índice inicial pode variar de 0 a len(given_list)-1. O índice final pode ser de start_index para len(given_list)-1. Você poderia usar um loop for aninhado para verificar todas as combinações possíveis.

3
Lev Levitsky

Aqui está uma implementação em Java, usando o Algoritmo de Kadane, que imprime os índices da maior soma. A implementação leva O(n) time e O(1) space.

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);
}
3
Skagen

A solução simples é percorrer a lista e tentar adicionar fatias até encontrar a melhor. Aqui eu também incluí a opção de retornar a sub-lista real também, por padrão, isso é falso. Eu usei defaultdict para esse propósito, porque é mais simples do que pesquisas.

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]])

Bônus: método de compreensão de lista:

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

Estou assumindo que essa é a questão de encontrar uma subseqüência em uma matriz que produz a soma máxima. Eu encontrei esse problema enquanto procurava por um problema SUBSET de soma máxima. 

A implementação Java para esta questão:

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;
}
1
Bhumik Thakkar

Ele está pedindo para você escolher uma subseção menor de uma lista, de modo que a soma menor da subseção seja a maior.

Se a lista é toda [1 2 3] positiva, então é claro que a subseção com a maior soma é apenas a soma da lista inteira [1 2 3] que é 6.

Se a lista é toda negativa [-1 -2 -3] então a subseção com a maior soma é nada [] que tem soma 0.

No entanto, se a lista tem alguns positivos e outros negativos, a decisão é mais difícil

[1 2 3 -100 3 4 5] você deve ver [3 4 5] e devolver 12

[1 2 3 -2 3 4 5] você deve usar tudo isso e retornar 16

1
Ric

Estou apresentando uma abordagem baseada em programação dinâmica. A ideia principal é que, à medida que percorremos o array, adicionar um novo elemento ao valor atual da soma deve aumentar o valor da soma ou prosseguir com o elemento atual e esquecer o antigo valor da soma.

Para acomodar matrizes com valores negativos, instanciamos nossas variáveis ​​com o primeiro elemento da matriz.

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 tempo de execução dessa abordagem é O (n) e a complexidade do espaço é O (1).

Se você quiser que a saída seja zero para os casos em que nenhum dos elementos é positivo, instancie as variáveis ​​cur_sum e best_sum com 0 e repita o primeiro elemento em vez do segundo elemento.

0
Vatsal Srivastava

se alguém estiver procurando por uma versão mais longa de um código, aqui está:

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
0
redx21

Essa distinção provavelmente não é importante para o OP, que parece estar apenas tentando entender como resolver o problema, mas achei que valeria a pena mencionar:

As outras soluções aqui envolvem repetidamente a soma de todas as subpartes da lista. Podemos evitar essas somas repetidas usando a programação dinâmica, pois, é claro, se já sabemos a soma de i para j, não precisamos adicioná-las novamente para obter a soma de i para j+1!

Isto é, faça uma matriz 2d das somas parciais, para que partsum[i, j] == sum(lst[i:j]). Algo como (usando um dicionário porque é mais fácil indexar com um array numpy seria igualmente fácil e mais eficiente):

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

Isto leva O (n ^ 2) tempo e memória, ao contrário de O (n ^ 3) tempo e O(1) memória para a abordagem de Lev/Inbar (se não for implementada como o primeiro exemplo de código da Inbar) .

0
Dougal

Este post introduz três maneiras de encontrar o subarray máximo de um array. 

  • Força bruta (O (n * n))
  • Dividir e conquistar (O (nlgn))
  • Algoritmo de Kadane (O (n))

Entre eles, o mais rápido é o algoritmo de Kadane, que tem uma complexidade de tempo de O (n).

0
PixelsTech