Clássico: Encontrar o maior subvector cuja soma é maxima

[Bruno Oliveira]

Considere-se um dado vector:

[−2, 1, −3, 4, −1, 2, 1, −5, 4]

Vemos que o subvector que tem a maior soma é:
[4, -1, 2, 1]

cuja soma é 6.

A vossa tarefa é escrever um programa em python que permita calcular a máxima soma existente num dado vector.

Boa programação,
Bruno

PS: Este problema vai servir para introduzir um paradigma de programação que tem vindo a tornar-se mais normalizado devido à sua frequente aparição em concursos de algoritmia, mas que é bastante complexo, e que é o de Programação Dinâmica.

[filipematos]

Mas para um vector com esse número de coordenadas e sub vector com 4 coordenadas ou com as que forem?

[Bruno Oliveira]

Obviamente, quero a solução do problema mais geral, em que o vector onde se vai procurar a solução tem coordenadas e o sub-vector terá coordenadas.

Dada uma sequência de n números , quero saber qual a sub-sequência de k números dessa sequência cuja soma é máxima.

[filipematos]

Foi o que eu pensei Muito em, vou trabalhar nisso!!! Postarei aqui o código quando o conseguir

[Bruno Oliveira]

Seria interessante que não o postasses logo, pois, este problema foi aqui postado por mim com dois própositos:

1. Trazer mais gente para o Python

2. Introduzir o conceito de Programação Dinâmica que eu próprio também estou a aprender

Reparei que a Adriana também veio ler o tópico.

Seria interessante e muito mais útil para todos (eu incluído) que discutissem aqui entre vocês algumas formas de abordar este problema (não necessariamente por programação dinâmica) e que descobrissem alguns aspectos interessantes sobre ele. O papel e o lápis são sempre os vossos melhores aliados nestes casos

Discutam todas as formas possíveis de resolver a questão, conjecturem sobre a validade e eficiência das mesmas, e no fim, irão aprender uma técnica de design de algoritmos espectacular!!

Bom brainstorming!!

[filipematos]

Excelente ideia É só as pessoas começarem a aparecer para se puder discutir

[Bruno Oliveira]

Exacto

Eu posso estar aqui para ajudar, se mais ninguém aparecer...

Mas gostaria que mais gente se envolvesse... aprender sozinho um assunto tão interessante como programação devia ser considerado crime!!!

PS: Obrigado Quark! por existires e me dares liberdade de expressão "geek"

[Tharis]

@Bruno Oliveira, não vejo razão para que cada um coloque aqui a sua solução. Se o problema é outros poderem ver e ficarem influenciados, existe a tag spoiler para isso. Quem quiser meter o código sob spoiler, coloque o código, seleccione-o e depois clique no botão spoiler (ao pé do bold, italic, ...).

Btw, bom problema para começar DP.

[Bruno Oliveira]

Eu disse isso mais por experiência própria visto que eu vou logo abrir o spoiler

Mas sim, creio que o problema é interessante para introduzir DP No entanto, e ainda para mim, partir deste problema para outros mais "mascarados" (no sentido de mais floreados, como os de competições de algoritmia) ainda é algo que não domino...

[jap]

Thks!

Bom desafio!
BTW, dentro em breve iremos (re)animar a secção Pitónica, com algumas novidades. Stay tuned!

[Bruno Oliveira]

Excelente!!!

Entretanto, uns desafios deste género são sempre interessantes!

[ruifm]

Obviamente, quero a solução do problema mais geral, em que o vector onde se vai procurar a solução tem coordenadas e o sub-vector terá coordenadas.

Dada uma sequência de n números , quero saber qual a sub-sequência de k números dessa sequência cuja soma é máxima.

eu não percebi bem o objectivo. É para generalizar o problema?
É para criar uma função a que dados todos os valores do vector, e dado o valor de k ( nº de coordenadas para o subvector), essa função retorna o subvector cuja soma é máxima?
isso até parece simples

[Bruno Oliveira]

Rui, não é assim tão simples não!

A tua função deve receber apenas um vector como argumento e retornar um número como output, em que o número é a máxima soma de um (qualquer) nº de elementos contíguos do vector. Deu para perceber?

[ruifm]

Temos de sequenciar todas as somas possiveis e achar a maxima?

[Bruno Oliveira]

Assim seria fácil...

Apesar dessa ser uma solução possível (é a solução chamada de força bruta ou brute force), gostaria que pensasses(m) numa forma mais directa e que não envolva sequenciar todas as somas possíveis