Larback - Retornando conhecimento

A beleza está à flor da pele, mas a feiúra vai até o osso!

Algoritmo de força bruta para o Maximum subarray problem

Um algoritmo de força bruta (ou busca completa, busca exaustiva) é um algoritmo que testa todas as possíveis soluções para um dado problema.
O Maximum subarray problem consiste em encontrar um subarray contíguo, dentro de um vetor numerico, com a maior soma possível. Por exemplo, para a sequência de valores -2, 1, -3, 4, -1, 2, 1, -5, 4; O subarray contíguo com a maior soma é 4, -1, 2, 1, com a soma 6.

O algoritmo abaixo utiliza a técnica de força bruta para resolver o problema:
#include <iostream>
using namespace std;
void bruteMax(int v[], int tam, int *li, int *ls, int *soma) {
	int temp;
	for (int i = 0; i < tam; i++){
		temp = v;
		for (int y = i+1; y < tam; y++){
			temp = temp + v[y];
			
			if (temp > *soma) {
				*soma = temp;
				*ls = y;
				*li = i;
			}
		}
	}
}
int main(int argc, char *argv[]) {
	// int entrada[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
	int entrada [] = {-1, 3, -5, 	, -3};
	//int entrada[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
	int tam = 10;
	int iSup = 0;
	int iInf = 0;
	int soma = entrada[0];
	bruteMax(entrada, tam, &iInf, &iSup, &soma);
	
	cout << "Soma: " << soma << endl;
	cout << "Inicio: " << iInf << endl;
	cout << "Fim: " << iSup;
	return 0;
}

A complexidade do algoritmo é O(n²)

Bons estudos.