o que é php?

php (pré-processador de hipertexto) é uma linguagem de script do lado do servidor amplamente usada para desenvolvimento da web. Ele permite que os desenvolvedores incorporem o código nos arquivos HTML, permitindo a criação de páginas dinâmicas da Web e interações com bancos de dados. O PHP é conhecido por sua simplicidade, versatilidade e extensos recursos de integração com bancos de dados populares. Oferece uma ampla gama de extensões e possui uma grande comunidade de desenvolvedores, garantindo amplos recursos e apoio.

Programa PHP para o maior subarray contíguo da soma

4 (-1) 2 1 = 6

a soma contígua máxima é = 6

usando o algoritmo de Kadane

O algoritmo de Kadane é um algoritmo eficiente usado para encontrar a soma máxima de uma subarray contígua dentro de uma determinada matriz. Foi desenvolvido por Jay Kadane em 1984.

O algoritmo funciona digitalizando iterativamente a matriz e mantendo duas variáveis: max_so_far e max_ending_here. Veja como o algoritmo funciona:

• inicialize max_so_far e max_ending_here variáveis ​​para o primeiro elemento da matriz ou para um valor mínimo (por exemplo, php_int_min) se a matriz contiver números negativos.

• iterar através da matriz do segundo elemento em diante.

• Para cada elemento, atualize max_ending_here adicionando o elemento atual a ele.

• Se max_ending_here se tornar negativo, redefini -lo para 0 porque a inclusão do elemento atual no subarray diminuirá a soma.

• se max_ending_here for maior que max_so_far, atualize max_so_far com a nova soma máxima.

• Repita as etapas 3 a 5 para os elementos restantes da matriz.

• Depois de itentar por toda a matriz, max_so_far manterá a soma máxima de um subarray contíguo.

• retorna max_so_far como resultado.

o algoritmo de Kadane tem uma complexidade de tempo de O (n), onde n é o tamanho da matriz, pois requer apenas uma única passagem pela matriz. Isso o torna uma solução eficiente para encontrar o subarray contíguo da soma máxima.

Exemplo

Saída

Maximum contiguous sum is 6

usando paradigma algorítmico: programação dinâmica

Exemplo

Saída

Maximum contiguous sum is 6

outra abordagem com índices de início e final

Exemplo

";
	echo "Starting index ". $start . "
".
			"Ending index " . $end . "
";
}
// Driver Code
$a = array(-2, 1, -3, 4, -1, 2, 1, -5, 4);
$n = sizeof($a);
$max_sum = maxSubArraySum($a, $n);
?>

Saída

Maximum contiguous sum is 6 
Starting index 3 
Ending index 6

Conclusão

O programa PHP para encontrar o maior subarray contíguo da soma utiliza programação dinâmica e algoritmo de Kadane. A abordagem de programação dinâmica é empregada para resolver com eficiência o problema, dividindo -o em submissas menores e armazenando as soluções em uma matriz.

O algoritmo de Kadane é um componente essencial do programa e é responsável por encontrar o maior subarray contíguo da soma. Ele itera sobre a matriz, atualizando continuamente a soma atual adicionando o elemento atual ou iniciando um novo subarray. A soma máxima encontrada é armazenada no $ maxsum variable. O programa lida com eficientemente números positivos e negativos na matriz. Ele identifica o subarray com a maior soma, acompanhando os índices de início e final, permitindo a extração do subarray usando o Array_slice.

utilizando programação dinâmica e algoritmo de Kadane, o programa alcança uma complexidade do tempo de O (n), onde n é o tamanho da matriz. Isso garante uma solução eficiente para encontrar a maior sub -direcionamento contígua da soma no PHP.