Kadane's Algorithm (Maximum Subarray)
Kadane's Algorithm finds the maximum sum of a contiguous subarray in O(n) time and O(1) space. Invented by Jay Kadane in 1984, it's an elegant dynamic programming algorithm that demonstrates optimal substructure. The algorithm maintains a running sum, resetting whenever it becomes negative, based on the insight that any negative sum prefix cannot contribute to the maximum sum.
Visualization
Interactive visualization for Kadane's Algorithm (Maximum Subarray)
Interactive visualization with step-by-step execution
Implementation
1function maxSubArray(nums: number[]): number {
2 let maxSum = nums[0];
3 let currentSum = nums[0];
4
5 for (let i = 1; i < nums.length; i++) {
6 currentSum = Math.max(nums[i], currentSum + nums[i]);
7 maxSum = Math.max(maxSum, currentSum);
8 }
9
10 return maxSum;
11}
12
13// With indices
14function maxSubArrayWithIndices(nums: number[]): { sum: number; start: number; end: number } {
15 let maxSum = nums[0];
16 let currentSum = nums[0];
17 let start = 0, end = 0, tempStart = 0;
18
19 for (let i = 1; i < nums.length; i++) {
20 if (currentSum < 0) {
21 currentSum = nums[i];
22 tempStart = i;
23 } else {
24 currentSum += nums[i];
25 }
26
27 if (currentSum > maxSum) {
28 maxSum = currentSum;
29 start = tempStart;
30 end = i;
31 }
32 }
33
34 return { sum: maxSum, start, end };
35}Deep Dive
Theoretical Foundation
Kadane's Algorithm uses dynamic programming with optimal substructure: at each position i, we decide whether to extend the previous subarray or start fresh. The recurrence is: maxEndingHere = max(arr[i], maxEndingHere + arr[i]). The key insight is that if maxEndingHere becomes negative, starting a new subarray from the current element is always better than extending the negative sum. We maintain maxSoFar to track the global maximum across all positions. The algorithm can be viewed as: for each element, we either add it to the existing sum (if positive) or start a new subarray from this element (if adding it would make sum worse). Time O(n), Space O(1). Can be modified to track start/end indices, handle all-negative arrays, or find maximum product subarray.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Stock trading - maximum profit in continuous period
Signal processing - finding strongest signal segment
Data analysis - identifying trends and patterns
Genomics - finding gene sequences with certain properties
Financial analysis - best performing time periods
Resource allocation - maximizing cumulative benefit
Quality control - identifying optimal production runs
Use Cases
Related Algorithms
0/1 Knapsack Problem
A classic optimization problem where you must select items with given weights and values to maximize total value without exceeding the knapsack's capacity. Each item can be taken only once (0 or 1). This is a fundamental problem in combinatorial optimization, resource allocation, and decision-making scenarios.
Longest Common Subsequence (LCS)
Finds the longest subsequence common to two sequences. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. This is fundamental in diff utilities, DNA sequence analysis, and version control systems like Git.
Edit Distance (Levenshtein Distance)
Edit Distance, also known as Levenshtein Distance, computes the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into another. Named after Soviet mathematician Vladimir Levenshtein who introduced it in 1965, this fundamental algorithm has applications in spell checking, DNA sequence analysis, natural language processing, and plagiarism detection.
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) finds the length of the longest subsequence in an array where all elements are in strictly increasing order. Unlike a subarray, a subsequence doesn't need to be contiguous - elements can be selected from anywhere as long as their order is preserved. This classic DP problem has two solutions: O(n²) dynamic programming and O(n log n) binary search with patience sorting. Applications include stock price analysis, scheduling, Box Stacking Problem, and Building Bridges Problem.