O algoritmo de Kadane é uma abordagem de programação dinâmica usada para resolver o problema de submatriz máxima, que envolve encontrar a submatriz contígua com a soma máxima em uma matriz de números. O algoritmo foi proposto por Jay Kadane em 1984 e possui uma complexidade de tempo de O(n).
História do algoritmo de Kadane:
O algoritmo de Kadane leva o nome de seu inventor, Jay Kadane, professor de ciência da computação na Carnegie Mellon University. Ele descreveu o algoritmo pela primeira vez em um artigo intitulado 'Maximum Sum Subarray Problem' publicado no Journal of the Association for Computing Machinery (ACM) em 1984.
O problema de encontrar o subarranjo máximo tem sido estudado por cientistas da computação desde a década de 1970. É um problema bem conhecido na área de projeto e análise de algoritmos e tem aplicações em uma ampla gama de áreas, incluindo processamento de sinais, finanças e bioinformática.
Antes do algoritmo de Kadane, outros algoritmos foram propostos para resolver o problema de submatriz máxima, como a abordagem de força bruta que verifica todas as submatrizes possíveis e o algoritmo de divisão e conquista. No entanto, estes algoritmos têm maiores complexidades de tempo e são menos eficientes que o algoritmo de Kadane.
O algoritmo de Kadane é amplamente utilizado na ciência da computação e se tornou um exemplo clássico de programação dinâmica. Sua simplicidade, eficiência e elegância o tornaram uma solução popular para o problema do subarranjo máximo e uma ferramenta valiosa no projeto e análise de algoritmos.
Funcionamento do Algoritmo de Kadene:
O algoritmo funciona iterando sobre o array e acompanhando a soma máxima do subarray que termina em cada posição. Em cada posição i, temos duas opções: adicionar o elemento na posição i ao subarranjo máximo atual ou iniciar um novo subarranjo na posição i. O máximo dessas duas opções é o subarranjo máximo que termina na posição i.
Mantemos duas variáveis, max_so_far e max_ending_here, para acompanhar a soma máxima vista até agora e a soma máxima que termina na posição atual, respectivamente. O algoritmo começa definindo ambas as variáveis para o primeiro elemento da matriz. Em seguida, iteramos sobre o array do segundo elemento até o final.
Em cada posição i, atualizamos max_ending_here pegando o máximo do elemento atual e o elemento atual adicionado ao subarray máximo anterior. Em seguida, atualizamos max_so_far para ser o máximo de max_so_far e max_ending_here.
encontrar números bloqueados no Android
O algoritmo retorna max_so_far, que é a soma máxima de qualquer submatriz na matriz.
Aqui está o processo passo a passo do Algoritmo de Kadane:
1. Inicialize duas variáveis, max_so_far e max_ending_here , para o primeiro elemento da matriz.
max_so_far = arr[0]
max_ending_here = arr[0]
2. Itere sobre o array do segundo elemento até o final:
para i de 1 a n-1 faça:
3. Calcule a soma máxima que termina na posição atual:
ordenação de array java
max_ending_here = max(arr[i], max_ending_here + arr[i])
4. Atualize max_so_far para ser o máximo de max_so_far e max_ending_here:
max_so_far = max(max_so_far, max_ending_here)
5. Retorne max_so_far como a soma máxima de qualquer submatriz na matriz.
A complexidade de tempo do algoritmo de Kadane é O(n), onde n é o comprimento da matriz de entrada. Isso o torna uma solução muito eficiente para o problema do subarranjo máximo.
Exemplo:
Vejamos um exemplo de como funciona o algoritmo de Kadane:
Suponha que temos o seguinte array de inteiros:
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Queremos encontrar a soma máxima do subarray deste array. Podemos aplicar o algoritmo de Kadane para resolver este problema.
Começamos inicializando duas variáveis:
max_so_far = INT_MIN; max_ending_here = 0;
Em seguida, iteramos pelo array, começando pelo segundo elemento:
expressão regular java $
for i in range(1, len(arr)):
Atualize a soma atual adicionando o elemento atual à soma anterior:
max_ending_here = max(arr[i], max_ending_here + arr[i])
Atualize a soma máxima vista até agora:
max_so_far = max(max_so_far, max_ending_here)
A cada iteração, atualizamos a soma atual adicionando o elemento atual à soma anterior ou iniciando um novo subarray no elemento atual. Em seguida, atualizamos a soma máxima vista até agora comparando-a com a soma atual.
Depois de iterar por todo o array, o valor de max_so_far será a soma máxima do subarray do array fornecido.
Neste exemplo, a soma máxima da submatriz é 6, que corresponde à submatriz [4, -1, 2, 1].
Implementação de código em Java:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print('Enter the size of the array : '); int n=sc.nextInt(); int[] arr=new int[n]; System.out.println('Enter the elements of the array : '); for(int i=0;i<n;i++){ arr[i]="sc.nextInt();" } int max_so_far="Integer.MIN_VALUE,max_ending_here=0;" for(int i="0;i<n;i++)" { max_ending_here+="arr[i];" if(max_so_far<max_ending_here){ if(max_ending_here<0){ max_ending_here="0;" system.out.print('the maximum contiguous sum in the array is : '+max_so_far); < pre> <p> <strong>Output</strong> </p> <pre> Enter the size of the array : 9 Enter the elements of the array : -2 1 -3 4 -1 2 1 -5 4 The Maximum contiguous sum in the array is : 6 </pre> <h3>Code Implementation in C++:</h3> <pre> #include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << 'maximum contiguous sum in the array is : '<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;></pre></n;i++){> Implementação de código em C++:
#include using namespace std; int main() { int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(a) / sizeof(a[0]); // Kadane's algorithm int max_so_far = INT_MIN, max_ending_here = 0; for (int i = 0; i <n; i++) { max_ending_here="max_ending_here" + a[i]; if (max_so_far < max_ending_here) max_so_far="max_ending_here;" (max_ending_here 0) } cout << \'maximum contiguous sum in the array is : \'<<max_so_far<<endl; return 0; pre> <p> <strong>Output</strong> </p> <pre> Maximum contiguous sum in the array is : 7 </pre> <h2>Advantages and Disadvantages of Kadane's algorithm:</h2> <h3>Advantages of Kadane's Algorithm:</h3> <ul> <tr><td>Efficiency:</td> Kadane's Algorithm has a time complexity of O(n), which makes it very efficient for solving the maximum subarray problem. This makes it a great solution for large datasets. </tr><tr><td>Simplicity:</td> Kadane's Algorithm is relatively easy to understand and implement compared to other algorithms for solving the maximum subarray problem, such as the divide-and-conquer algorithm. </tr><tr><td>Space Complexity:</td> Kadane's Algorithm has a space complexity of O(1), which means it uses a constant amount of memory irrespective of the size of the input array. </tr><tr><td>Dynamic Programming:</td> Kadane's Algorithm is a classic example of dynamic programming, a technique that breaks down a problem into smaller subproblems and stores the solutions to these subproblems to avoid redundant computation. </tr></ul> <h3>Disadvantages of Kadane's Algorithm:</h3> <ul> <tr><td>Only finds sum and not the subarray itself:</td> Kadane's Algorithm only finds the maximum sum of the subarray and not the actual subarray itself. If you need to find the subarray that has the maximum sum, you will need to modify the algorithm accordingly. </tr><tr><td>Does not handle negative numbers well:</td> If an input array has only negative numbers, the algorithm will return the maximum negative number instead of 0. This can be overcome by adding an additional step to the algorithm to check if the array has only negative numbers. </tr><tr><td>Not suitable for non-contiguous subarrays:</td> Kadane's Algorithm is specifically designed for contiguous subarrays and may not be suitable for solving problems that involve non-contiguous subarrays. </tr></ul> <h2>Applications of Kadane's algorithm:</h2> <p>There are some of its applications like the following:</p> <ul> <tr><td>Maximum subarray sum:</td> As we saw in the example above, Kadane's algorithm is used to find the maximum subarray sum of an array of integers. This is a common problem in computer science and has applications in data analysis, financial modeling, and other fields. </tr><tr><td>Stock trading:</td> Kadane's algorithm can be used to find the maximum profit that can be made by buying and selling a stock on a given day. The input to the algorithm is an array of stock prices, and the output is the maximum profit that can be made by buying and selling the stock at different times. </tr><tr><td>Image processing:</td> Kadane's algorithm can be used in image processing applications to find the largest contiguous area of pixels that meet a certain condition, such as having a certain color or brightness. This can be useful for tasks such as object recognition and segmentation. </tr><tr><td>DNA sequencing:</td> Kadane's algorithm can be used in bioinformatics to find the longest subsequence of DNA that meets certain conditions. For example, it can be used to find the longest common subsequence between two DNA sequences or to find the longest subsequence that does not contain certain patterns. </tr><tr><td>Machine learning:</td> Kadane's algorithm can be used in some machine learning applications, such as reinforcement learning and dynamic programming, to find the optimal policy or action sequence that maximizes a reward function. </tr></ul> <p>Therefore, we can say the advantages of Kadane's Algorithm make it a great solution for solving the maximum subarray problem, especially for large datasets. However, its limitations must be considered when using it for specific applications.</p> <hr></n;> Vantagens e desvantagens do algoritmo de Kadane:
Vantagens do Algoritmo de Kadane:
Desvantagens do Algoritmo de Kadane:
Aplicações do algoritmo de Kadane:
Existem algumas de suas aplicações como as seguintes:
Portanto, podemos dizer que as vantagens do Algoritmo de Kadane o tornam uma ótima solução para resolver o problema do subarranjo máximo, especialmente para grandes conjuntos de dados. No entanto, suas limitações devem ser consideradas ao utilizá-lo para aplicações específicas.