#include <stdio.h>
// Function to find the maximum sum of a contiguous subarray
int kadane(int arr[], int n) {
// Initialize variables
int max_current = arr[0];
int max_global = arr[0];
// Iterate through the array
for (int i = 1; i < n; i++) {
// Update max_current to be the maximum of the current element or
// the current element plus the previous max_current
max_current = (arr[i] > max_current + arr[i]) ? arr[i] : max_current + arr[i];
// Update max_global to be the maximum of max_global and max_current
if (max_current > max_global) {
max_global = max_current;
}
}
// Return the result
return max_global;
}
int main() {
// Example array
int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
// Find the maximum sum subarray
int max_sum = kadane(arr, n);
// Print the result
printf("Maximum sum of contiguous subarray: %d\n", max_sum);
return 0;
}
Kadane’s Algorithm is a highly efficient method for finding the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It works by iterating through the array and maintaining two values: the maximum sum of the subarray ending at the current position and the overall maximum sum encountered so far. By comparing and updating these values as it processes each element, the algorithm ensures that it captures the largest possible sum of consecutive elements. This approach has a time complexity of O(n), making it ideal for large arrays due to its linear runtime. Kadane’s Algorithm is widely used in various applications, including financial analysis and computational problems involving subarray optimization.
Kadane's Algorithm, named after the American computer scientist Joseph Kadane who introduced it in 1984, addresses a classic problem in computer science: finding the maximum sum of a contiguous subarray. The problem gained prominence due to its applicability in various fields, such as finance, where it is used to calculate the maximum profit from a sequence of stock prices, or in signal processing and other optimization tasks. Before Kadane's work, solutions to this problem often involved brute-force methods with a time complexity of O(n^2), which were inefficient for large datasets.
Kadane's Algorithm exemplifies the concept of dynamic programming, a powerful paradigm used to solve optimization problems by breaking them down into simpler subproblems. Dynamic programming involves solving each subproblem just once and storing the results to avoid redundant calculations. In the context of Kadane's Algorithm, dynamic programming is employed to maintain two key variables: `max_current`, which represents the maximum sum of the subarray ending at the current position, and `max_global`, which stores the maximum sum encountered so far. By iterating through the array and updating these values, Kadane's Algorithm efficiently finds the solution with a time complexity of O(n), demonstrating the effectiveness of dynamic programming in optimizing complex problems.