Esse cenário pode ser modelado como um problema de se encontrar o subvetor de maior valor em um vetor. Um algoritmo de divisão e conquista pode ser...

Esse cenário pode ser modelado como um problema de se encontrar o subvetor de maior valor em um vetor. Um algoritmo de divisão e conquista pode ser implementado para resolver esse problema, conforme apresentado no pseudocódigo abaixo. O algoritmo recebe um vetor A delimitado pelos índicess min e max . O algoritmo faz uso de um procedimento auxiliar, de complexidade Θ(n) , chamado subvetor-geral, responsável por identificar a maior soma dentro de um subvetor informado. Máximo-subvetor(A, min, max) 01. se max = min então ; ‍ 02. retorna (min, max, A[min]); 03. senão ; ‍ 04. meio = (min + max) / 2; 05. (esq-min, esq-max, soma-esq) = Máximo-Subvetor(A, min, meio); 06. (dir-min, dir-max, soma-dir) = Máximo-Subvetor(A, meio + 1, max); 07. (geral-min, geral-max, soma-geral) = Subvetor-Geral(A, min, meio, max); 08. se soma-esq ≥ soma-dir e soma-esq ≥ soma-geral; 09. retorna (esq-min, esq-max, soma-esq); 10. se soma-dir ≥ soma-esq e soma-dir ≥ soma-geral; 11. retorna (dir-min, dir-max, soma-dir); 12. senão retorna (geral-min, geral-max, soma-geral).