Hubbry Logo
Maximum subarray problemMaximum subarray problemMain
Open search
Maximum subarray problem
Community hub
Maximum subarray problem
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Maximum subarray problem
Maximum subarray problem
Maximum subarray problem
View on Wikipedia
from Wikipedia
Not found
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Maximum subarray problem

View on Grokipedia
from Grokipedia
The maximum subarray problem, also known as the maximum contiguous subarray sum problem, involves finding a contiguous subarray within a given one-dimensional array of integers that yields the largest possible sum. This classic algorithmic challenge was first popularized in 1984 by Jon Bentley in his "Programming Pearls" column in Communications of the ACM, where he credited statistician Jay Kadane with developing an efficient linear-time solution using dynamic programming. Bentley's exposition framed the problem as a practical example of algorithm design, contrasting naive quadratic-time approaches with optimized methods that scan the array once while tracking the maximum sum ending at each position. Kadane's algorithm, often simply called Kadane's algorithm, achieves O(n) time complexity for an array of length n by maintaining two variables: the maximum subarray sum ending at the current position (updated to the maximum of the current element or the sum of the previous ending sum plus the current element) and the global maximum sum encountered so far. This approach exemplifies divide-and-conquer alternatives as well, though they typically run in O(n log n) time, highlighting trade-offs in algorithm simplicity and efficiency. Beyond its pedagogical value in teaching dynamic programming and analysis, the maximum subarray problem has practical applications across domains such as , where it identifies peak signal segments; , for detecting profitable trading periods in stock price sequences; and , for locating high-scoring contiguous segments in DNA or protein sequences. In image processing and , extensions to two-dimensional arrays find maximum-sum rectangular regions, aiding tasks like and feature extraction. The problem's generalizations, including circular arrays or k-maximum subarrays, further underscore its foundational role in algorithm research and optimization challenges.

Problem Description

Formal Statement

The maximum subarray problem consists of identifying a contiguous portion of a one-dimensional array that yields the largest possible sum of its elements. Formally, given an array AA of nn integers indexed from 1 to nn, the task is to find indices ii and jj such that 1≤i≤j≤n1 \leq i \leq j \leq n and the sum S=∑k=ijAS = \sum_{k=i}^{j} A is maximized over all possible contiguous subarrays. The elements of the array AA may be positive, negative, or zero, and the subarray must be non-empty in the standard version of the problem. The primary output is the maximum sum SS, although some formulations also return the starting and ending indices ii and jj. A variant of the problem permits the empty subarray, which has a sum of 0 and is selected when all elements are negative; the standard case, however, requires a non-empty subarray.

Illustrative Example

To illustrate the maximum subarray problem, consider the array A=[−2,1,−3,4,−1,2,1,−5,4]A = [-2, 1, -3, 4, -1, 2, 1, -5, 4], which contains a mix of positive and negative integers to highlight the need to identify contiguous segments where positives outweigh negatives. This example demonstrates the task of finding the non-empty contiguous subarray with the largest possible sum by manually examining possibilities. A manual approach involves systematically computing sums for subarrays of increasing lengths to build intuition. For single-element subarrays (length 1), the sums are simply the elements: -2, 1, -3, 4, -1, 2, 1, -5, 4, with the largest being 4 (from index 3). For length 2 subarrays: sums are -1 (indices 0-1), -2 (1-2), 1 (2-3), 3 (3-4), 1 (4-5), 3 (5-6), -4 (6-7), -1 (7-8), where the largest is 3. Extending to length 3: sums include -4 (0-2), 2 (1-3), 0 (2-4), 5 (3-5), 2 (4-6), -2 (5-7), 0 (6-8), with 5 now the leading candidate (indices 3-5). For length 4: sums such as 0 (0-3), 1 (1-4), 2 (2-5), 6 (3-6), -3 (4-7), 2 (5-8), where 6 emerges as a new high (indices 3-6). Continuing this process for lengths 5 through 9 reveals no higher sums; for instance, the full array (length 9) sums to 1 (indices 0-8), and other longer segments like indices 3-8 sum to 5. The complete manual enumeration confirms the maximum sum of 6 from the subarray [4, -1, 2, 1] (indices 3 to 6, 0-based). The table below presents representative subarrays across lengths, including the optimal one (highlighted), all-negative cases, and others for comparison:
Start IndexEnd IndexSubarraySum
00[-2]-2
22[-3]-3
77[-5]-5
334
34[4, -1]3
35[4, -1, 2]5
36[4, -1, 2, 1]6
56[2, 1]3
68[1, -5, 4]0
884
08[-2, 1, -3, 4, -1, 2, 1, -5, 4]1
Subarrays consisting only of negative numbers, such as [-2], [-3], or [-5], yield negative sums and fail to be maximum because the array includes positive elements that produce higher values alone or in combination. Similarly, subarrays incorporating large negatives without adequate positive offset, like [1, -5, 4] (sum 0) or the full array (sum 1), underperform compared to those that exclude or minimize such drags, emphasizing the importance of contiguity in balancing contributions.

Historical Background

Origins in Computing

The maximum subarray problem emerged in the late 1970s within the field of , particularly in contexts involving and . In 1977, Swedish mathematician Ulf Grenander at proposed the problem as a simplified one-dimensional model for in digitized image analysis, where identifying contiguous regions with the highest aggregate values could reveal patterns in noisy data. This formulation arose from Grenander's work on two-dimensional arrays, which proved computationally intensive, leading to the reduction to a linear sequence to study contiguous substructures efficiently. The problem's roots in these early computing applications highlighted motivations around processing sequential data in resource-constrained environments, such as early systems. During this period, the problem gained traction in academic discussions, notably through a course at led by Jon Bentley, Michael Shamos, and Joseph Kadane. Focused on stochastic , the explored the problem's implications for worst-case and average-case performance in sequence processing tasks, bridging statistics and . Grenander had shared his ideas with Shamos earlier that year, prompting explorations of the problem's computational challenges in one-dimensional forms relevant to emerging data structures research. This represented an early conceptualization of the problem within formal , emphasizing its utility in analyzing linear arrays from real-world signals. A pivotal popularization occurred in 1984 through Jon Bentley's column in Communications of the ACM, which detailed the problem's design techniques and connected it to broader development in . This publication introduced the maximum subarray problem to a wider of programmers and educators, framing it as a example in early algorithm textbooks and structures courses for teaching sequence processing concepts. Such inclusions underscored its role in foundational curricula, often illustrated through applications like evaluating consecutive metrics in linear streams.

Key Developments and Contributors

The efficient algorithms for the maximum subarray problem emerged in the late 1970s during a seminar at involving computer scientists Jon Bentley and Michael Shamos, alongside statistician Joseph (Jay) Kadane. Shamos developed an initial divide-and-conquer approach achieving O(n log n) , which Bentley later detailed in his 1984 publication on algorithm design techniques, marking a significant advancement over brute-force methods by leveraging recursive decomposition to identify crossing subarrays. Kadane contributed the seminal linear-time dynamic programming solution, O(n), by formalizing an incremental scan that tracks the maximum subarray sum ending at each position. This algorithm, now widely known as Kadane's algorithm, was first described in the same 1984 Communications of the ACM article by , though a 2023 paper by Kadane provides his firsthand account of its origins in the late 1970s seminar discussions. Subsequent refinements in the 1980s and 1990s focused on edge cases, such as arrays with all negative elements or allowing empty subarrays (with sum 0). Kadane's original formulation returns the largest single element in all-negative cases, while variants permitting empty subarrays reset the sum to 0 when beneficial, ensuring robustness in diverse inputs; these adaptations appeared in pedagogical discussions and implementations through the early .

Practical Applications

In Algorithm Design and Education

The maximum subarray problem is a cornerstone in introductory algorithms courses at universities worldwide, serving to introduce students to key paradigms such as brute-force enumeration, divide-and-conquer recursion, and dynamic programming optimization. Instructors use it to highlight efficiency trade-offs: the quadratic brute-force method exhaustively checks all subarrays, the divide-and-conquer approach achieves O(n log n) time by recursively partitioning the array and combining crossing subarrays, and dynamic programming yields linear time by building on partial solutions. This progression helps learners grasp how problem and of computations reduce from exponential possibilities to polynomial efficiency. A prominent example appears in the textbook Introduction to Algorithms (commonly known as CLRS) by , , Ronald L. Rivest, and Clifford Stein, where Chapter 4 dedicates Section 4.1 to the problem as an entry point into divide-and-conquer techniques. The text includes exercises that extend the core problem, such as devising a non-recursive linear-time algorithm or writing for the brute-force variant, encouraging students to explore edge cases like all-negative arrays and implement optimizations themselves. These homework problems reinforce understanding of recursive design while preparing learners for real implementation challenges. The problem's pedagogical strength also stems from its illustration of foundational concepts like prefix sums, which track cumulative totals to avoid redundant calculations in dynamic programming, and the interplay between local optima (maximum sums ending at each position) and the global optimum (the overall maximum). By contrasting suboptimal local choices—such as discarding negative prefixes—with strategies that maintain the best ending sum, it teaches the nuances of greedy-like decisions within a dynamic framework. Beyond academia, the maximum subarray problem has been a standard coding interview question at major technology firms, evaluating candidates' skills in recognizing inefficiencies in naive solutions and deriving optimal under time constraints. Interviewers often start with the brute-force approach to assess basic understanding before probing for improvements like Kadane's , testing the ability to balance correctness with performance. This practice underscores its role in professional design training, where it exemplifies transitioning from theoretical knowledge to practical optimization.

In Real-World Data Processing

In financial time series analysis, the maximum subarray problem facilitates the identification of contiguous periods in stock price data that maximize cumulative returns, representing the most profitable sequences for holding investments. By treating daily price changes as array elements, the problem models the selection of optimal buy and sell points, where the subarray sum corresponds to the net gain over that interval. This application is particularly useful for retrospective performance evaluation and optimization in volatile markets. In bioinformatics, the maximum subarray problem extends to analyzing matrices, where it identifies subsets of genes exhibiting high expression levels across specific sample groups, aiding in discovery and subtype classification. For instance, in datasets, algorithms solving the max-sum submatrix variant—building on one-dimensional subarray techniques—pinpoint non-contiguous but maximally expressive gene-sample combinations, outperforming traditional by handling outliers and heterogeneity more robustly. Experiments on real datasets with thousands of genes demonstrate that approaches achieve near-optimal solutions in seconds, enabling efficient mining of biologically relevant patterns like enriched terms. In , the maximum subarray problem detects bursts of maximum energy or activity in sequential data from audio, sensors, or RF signals, crucial for tasks like and event localization. Kadane's algorithm is applied to arrays of signal metrics, such as reconstruction errors in spoken term detection, to isolate contiguous segments with the highest summed intensity, thereby hypothesizing query occurrences efficiently. This linear-time method supports real-time processing in resource-constrained environments. For preprocessing, particularly in sequential from IoT streams, the maximum subarray problem enables by selecting contiguous segments that capture peak patterns or anomalies, enhancing model inputs for time-series prediction. In pipelines, it accelerates subwindow searches over feature maps to identify discriminative regions, reducing computational overhead while maintaining accuracy in high-dimensional .

Solution Algorithms

Brute-Force Method

The brute-force method solves the maximum subarray problem by systematically evaluating the sum of every possible contiguous subarray in the input array of length nn. This is accomplished through two nested loops: the outer loop iterates over each possible starting index ii from 1 to nn, and the inner loop iterates over each possible ending index jj from ii to nn, accumulating the sum from AA to AA and updating the global maximum if the current sum exceeds it. The approach ensures completeness by considering all n(n+1)2\frac{n(n+1)}{2} subarrays, but its time complexity is Θ(n2)\Theta(n^2) due to the quadratic number of summations performed. The following implements this method, returning the maximum subarray sum (adapted from the standard formulation in algorithmic literature):

BRUTE-FORCE-MAXIMUM-SUBARRAY-SUM(A) n ← length[A] max_sum ← -∞ for i ← 1 to n current_sum ← 0 for j ← i to n current_sum ← current_sum + A[j] if current_sum > max_sum max_sum ← current_sum return max_sum

BRUTE-FORCE-MAXIMUM-SUBARRAY-SUM(A) n ← length[A] max_sum ← -∞ for i ← 1 to n current_sum ← 0 for j ← i to n current_sum ← current_sum + A[j] if current_sum > max_sum max_sum ← current_sum return max_sum

This pseudocode runs in Θ(n2)\Theta(n^2) time, as each of the O(n)O(n) outer iterations performs O(n)O(n) work in the inner loop. To illustrate the computation, consider an of length 8: A=[−2,1,−3,4,−1,2,1,−5]A = [-2, 1, -3, 4, -1, 2, 1, -5]. The method evaluates all 36 contiguous subarrays, computing their sums as shown in the table below (using 1-based indexing). The maximum sum found is 6, corresponding to the subarray from index 4 to 7 (4+(−1)+2+14 + (-1) + 2 + 1).
Starting Index (i)Ending Index (j)Subarray Sum
11-2
12-1
13-4
140
15-1
161
172
18-3
221
23-2
242
251
263
274
28-1
33-3
341
350
362
373
38-2
444
453
465
476
481
55-1
561
572
58-3
662
673
68-2
771
78-4
88-5
The brute-force method offers simplicity in both conception and implementation, requiring no advanced data structures or recursive strategies, and it is guaranteed to produce the correct result for any input array of reasonable size, such as n≤100n \leq 100. However, its Θ(n2)\Theta(n^2) makes it inefficient and impractical for large arrays; for example, with n=105n = 10^5, it would require on the order of 101010^{10} operations, exceeding the capabilities of typical computing hardware which processes roughly 10910^9 operations per second.

Divide-and-Conquer Approach

The divide-and-conquer approach solves the maximum subarray problem by recursively dividing the array into two halves, solving the subproblems independently, and then combining the results by considering subarrays that cross the midpoint. This strategy achieves O(n log n) time complexity, improving over the O(n²) brute-force method by exploiting the divide-and-combine structure to avoid exhaustive enumeration. The algorithm proceeds in three main phases: divide, conquer, and combine. In the divide phase, the array from indices low to high is split at the midpoint mid = floor((low + high) / 2). The conquer phase recursively computes the maximum subarray sum in the left half (low to mid) and the right half (mid + 1 to high). For the combine phase, it calculates the maximum crossing subarray sum by finding the maximum suffix sum from the left half (starting from mid and moving leftward, accumulating sums and tracking the maximum) and the maximum prefix sum from the right half (starting from mid + 1 and moving rightward), then adding these two values to get the crossing sum. The overall maximum is the largest among the left maximum, right maximum, and crossing maximum. The base case occurs when low == high, returning the array element. Here is the pseudocode for the algorithm, adapted from the original formulation:

function maxSubarraySum(low, high): if low == high: return array[low] mid = floor((low + high) / 2) // Maximum subarray sum in left half leftMax = maxSubarraySum(low, mid) // Maximum subarray sum in right half rightMax = maxSubarraySum(mid + 1, high) // Maximum crossing sum leftSuffix = 0 maxLeftSuffix = -∞ for i from mid downto low: leftSuffix += array[i] maxLeftSuffix = max(maxLeftSuffix, leftSuffix) rightPrefix = 0 maxRightPrefix = -∞ for i from mid + 1 to high: rightPrefix += array[i] maxRightPrefix = max(maxRightPrefix, rightPrefix) crossingMax = maxLeftSuffix + maxRightPrefix return max(leftMax, rightMax, crossingMax)

function maxSubarraySum(low, high): if low == high: return array[low] mid = floor((low + high) / 2) // Maximum subarray sum in left half leftMax = maxSubarraySum(low, mid) // Maximum subarray sum in right half rightMax = maxSubarraySum(mid + 1, high) // Maximum crossing sum leftSuffix = 0 maxLeftSuffix = -∞ for i from mid downto low: leftSuffix += array[i] maxLeftSuffix = max(maxLeftSuffix, leftSuffix) rightPrefix = 0 maxRightPrefix = -∞ for i from mid + 1 to high: rightPrefix += array[i] maxRightPrefix = max(maxRightPrefix, rightPrefix) crossingMax = maxLeftSuffix + maxRightPrefix return max(leftMax, rightMax, crossingMax)

This assumes 0-based or 1-based indexing as per the implementation; the crossing computation takes O(n time per level of . To illustrate, consider the A = [3, -7, 4, 2, -1] with indices 1 to 5. The top-level call maxSubarraySum(1,5) sets mid=3.
  • Recurse on left (1-3): mid=2.
    • Left-left (1-2): mid=1.
      • Base (1-1): 3
      • Base (2-2): -7
      • Crossing (1-2): leftSuffix from 1: 3 (max=3); rightPrefix from 2: -7 (max=-7); crossing=3 + (-7) = -4
      • Max for 1-2: max(3, -7, -4)=3
    • Right-left (3-3): 4
    • Crossing (1-3): leftSuffix from 2 to 1: -7 (max=-7), then -7+3=-4 (max=-4); rightPrefix from 3: 4 (max=4); crossing=-4 + 4 = 0
    • Max for 1-3: max(3, 4, 0)=4
  • Recurse on right (4-5): mid=4.
    • Base (4-4): 2
    • Base (5-5): -1
    • Crossing (4-5): leftSuffix from 4: 2 (max=2); rightPrefix from 5: -1 (max=-1); crossing=2 + (-1) = 1
    • Max for 4-5: max(2, -1, 1)=2
  • Top crossing (1-5): leftSuffix from 3 to 1: 4 (max=4), then 4 + (-7)=-3 (max=4), -3 + 3=0 (max=4); rightPrefix from 4 to 5: 2 (max=2), 2 + (-1)=1 (max=2); crossing=4 + 2 = 6
  • Overall max: max(4, 2, 6)=6 (subarray from index 3 to 4: [4, 2])
The recursion tree has depth log n ≈ 3 levels, with crossing computations at each node. This divide-and-conquer method was proposed by Jon Bentley in his 1984 Communications of the ACM column as an efficient recursive technique, serving as a precursor to subsequent linear-time s.

Kadane's Dynamic Programming

Kadane's dynamic programming offers a linear-time solution to the maximum subarray problem by scanning the input array once and maintaining running maxima. Attributed to statistician Jay Kadane and first detailed in Jon Bentley's 1984 article on algorithm design techniques, it leverages dynamic programming principles to compute the optimal subarray sum without explicit table storage. The core idea involves tracking the maximum subarray sum ending at the current position—termed the "best ending here"—while simultaneously updating the overall maximum sum discovered. For each element, this current maximum is set to the larger of the element itself (starting a new subarray) or the sum of the previous current maximum plus the element (extending the subarray). If the previous sum is negative, extending it would only decrease the total, so resetting to the current element alone is preferable. This process ensures that at every step, the algorithm considers all possible subarrays ending at the current index implicitly, capturing the global optimum through iterative updates. The standard pseudocode for non-empty subarrays initializes both the current and global maxima to the first array element and proceeds as follows:

max_current = A[0] max_global = A[0] for i = 1 to n-1: max_current = max(A[i], max_current + A[i]) max_global = max(max_global, max_current) return max_global

max_current = A[0] max_global = A[0] for i = 1 to n-1: max_current = max(A[i], max_current + A[i]) max_global = max(max_global, max_current) return max_global

This formulation guarantees a non-empty result and runs in O(n) time with O(1) extra space. Consider the illustrative array A = [3, -7, 4, 2, -1] to walkthrough the execution:
  • Initialize: max_current = 3, max_global = 3 (subarray ).
  • At i=1 (-7): max_current = max(-7, 3 + (-7)) = max(-7, -4) = -4; max_global remains 3 (since -4 < 3).
  • At i=2 (4): max_current = max(4, -4 + 4) = max(4, 0) = 4; max_global = 4 (4 > 3).
  • At i=3 (2): max_current = max(2, 4 + 2) = max(2, 6) = 6; max_global = 6 (6 > 4).
  • At i=4 (-1): max_current = max(-1, 6 + (-1)) = max(-1, 5) = 5; max_global remains 6 (5 < 6).
The algorithm yields a maximum sum of 6 from the subarray [4, 2].

Algorithm Analysis

Time and Space Complexity

The brute-force method for the maximum subarray problem enumerates all possible contiguous subarrays by iterating over every pair of start and end indices, computing each subarray sum using prefix sums in constant time, resulting in O(n²) time complexity due to the nested loops each running in O(n) iterations. This approach requires O(1) additional space, as it only stores a few variables for the current sum and maximum. The divide-and-conquer algorithm recursively splits the array into two halves, solves the subproblems, and computes the maximum crossing subarray in O(n) time by finding the maximum suffix sum from the left half and prefix sum from the right half. The recurrence relation is T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n), which, by the master theorem (case 2, where the work at each level dominates), yields O(n log n) time complexity. Space usage is O(log n) from the recursion depth. Kadane's algorithm processes the array in a single pass, tracking the maximum sum ending at the current position and updating the global maximum, achieving O(n) time complexity through linear traversal and O(1) space by using only constant variables without auxiliary storage. Any correct algorithm for the maximum subarray problem has an asymptotic lower bound of Ω(n) time complexity, as it must read and consider all input elements to identify the optimal subarray.
AlgorithmTime ComplexitySpace ComplexityOperations for n=10³Operations for n=10⁴Operations for n=10⁵Operations for n=10⁶
Brute-ForceO(n²)O(1)~10⁶~10⁸~10¹⁰~10¹²
Divide-and-ConquerO(n log n)O(log n)~10⁴~1.3×10⁵~1.7×10⁶~2×10⁷
Kadane'sO(n)O(1)~10³~10⁴~10⁵~10⁶

Handling Edge Cases

The maximum subarray problem requires careful handling when all elements in the input array are negative, as the optimal solution is then the single largest (least negative) element rather than any multi-element subarray. In Kadane's dynamic programming algorithm, this is addressed by initializing both the current subarray sum and the global maximum sum to the first element of the array, ensuring that the algorithm selects the maximum individual element without erroneously resetting to zero during updates. This modification guarantees correctness for all-negative inputs, where the maximum sum equals the maximum element value. If the problem variant allows empty subarrays with a sum of zero, the algorithm must further adapt to return 0 when all possible non-empty subarray sums are negative, prioritizing the empty subarray as the maximum. A common implementation achieves this by modifying the update rule for the current subarray sum to take the maximum of 0 and the accumulated sum plus the current element, effectively discarding negative prefixes and allowing the empty case implicitly. For example, in pseudocode:

max_so_far = 0 max_ending_here = 0 for each element x in the array: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far

max_so_far = 0 max_ending_here = 0 for each element x in the array: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far

This variant correctly returns 0 for all-negative arrays while maintaining O(n) time complexity. To compute not only the maximum sum but also the starting and ending indices of the corresponding subarray, Kadane's algorithm can be extended with additional tracking variables. A temporary start index is reset whenever a new subarray begins (i.e., when the current sum would be better started anew), and the global start and end indices are updated only when the global maximum is improved. This ensures the indices correspond to the first occurrence of the maximum sum subarray if multiple exist. The following pseudocode illustrates this for the non-empty subarray case:

if the array is empty: return 0, -1, -1 // or handle as per problem specification max_so_far = array[0] max_ending_here = array[0] start = 0 end = 0 temp_start = 0 for i = 1 to array.length - 1: if max_ending_here + array[i] > array[i]: max_ending_here += array[i] else: max_ending_here = array[i] temp_start = i if max_ending_here > max_so_far: max_so_far = max_ending_here start = temp_start end = i return max_so_far, start, end

if the array is empty: return 0, -1, -1 // or handle as per problem specification max_so_far = array[0] max_ending_here = array[0] start = 0 end = 0 temp_start = 0 for i = 1 to array.length - 1: if max_ending_here + array[i] > array[i]: max_ending_here += array[i] else: max_ending_here = array[i] temp_start = i if max_ending_here > max_so_far: max_so_far = max_ending_here start = temp_start end = i return max_so_far, start, end

For single-element arrays (n=1), this returns the element itself with start and end both at index 0; for empty arrays (n=0), the output is explicitly defined as sum 0 with invalid indices (e.g., -1) to indicate no subarray exists.

Extensions and Variants

Circular Arrays

The circular maximum subarray problem extends the standard formulation to arrays where subarrays may wrap around from the end to the beginning, allowing contiguous segments that span the array's boundary. In this variant, the array is treated as circular, meaning the last element connects to the first, but each element can be included at most once in the subarray. This arises in scenarios where data is naturally cyclic, such as in ring buffers or periodic signals. The solution leverages Kadane's algorithm applied twice: once for the standard (non-wrapping) maximum subarray sum, and once to find the minimum subarray sum, which is used to compute the wrapping case as the total array sum minus the minimum subarray sum. The overall maximum is then the larger of these two values. To find the minimum subarray sum efficiently, Kadane's algorithm can be adapted by tracking the minimum cumulative sum during a single pass, or equivalently by negating all array elements and applying the standard Kadane's algorithm to find the "maximum" on the negated array (which yields the negative of the minimum). An occurs if all elements are non-positive, where the maximum is the largest single element, and if the minimum sum equals the total sum (all non-positive), the wrapping case is ignored. This approach maintains O(n time complexity. Here is pseudocode for the algorithm:

function maxCircularSubarray(arr): if arr is empty: return 0 n = length(arr) totalSum = sum(arr) # Standard Kadane for max subarray sum maxSum = kadane(arr) # Min subarray sum using modified Kadane minSum = kadane_negated(arr) # or track min in same pass as max # Wrapping max if minSum == totalSum: return maxSum wrapMax = totalSum - minSum return max(maxSum, wrapMax) function kadane(arr): maxCurrent = maxGlobal = arr[0] for i = 1 to n-1: maxCurrent = max(arr[i], maxCurrent + arr[i]) if maxCurrent > maxGlobal: maxGlobal = maxCurrent return maxGlobal function kadane_negated(arr): # Equivalent to min Kadane minCurrent = minGlobal = arr[0] for i = 1 to n-1: minCurrent = min(arr[i], minCurrent + arr[i]) if minCurrent < minGlobal: minGlobal = minCurrent return minGlobal

function maxCircularSubarray(arr): if arr is empty: return 0 n = length(arr) totalSum = sum(arr) # Standard Kadane for max subarray sum maxSum = kadane(arr) # Min subarray sum using modified Kadane minSum = kadane_negated(arr) # or track min in same pass as max # Wrapping max if minSum == totalSum: return maxSum wrapMax = totalSum - minSum return max(maxSum, wrapMax) function kadane(arr): maxCurrent = maxGlobal = arr[0] for i = 1 to n-1: maxCurrent = max(arr[i], maxCurrent + arr[i]) if maxCurrent > maxGlobal: maxGlobal = maxCurrent return maxGlobal function kadane_negated(arr): # Equivalent to min Kadane minCurrent = minGlobal = arr[0] for i = 1 to n-1: minCurrent = min(arr[i], minCurrent + arr[i]) if minCurrent < minGlobal: minGlobal = minCurrent return minGlobal

For example, consider the array [5, -3, 5]. The standard maximum subarray sum is 5 (either single element). The total sum is 7, and the minimum subarray sum is -3, so the wrapping maximum is 7 - (-3) = 10, from the subarray [5, 5] (indices 0 and 2, wrapping around). The overall maximum is 10. This variant finds applications in processing circular buffers, common in streaming data systems like real-time signal processing or queue-based data ingestion, where the most recent window of values may wrap around fixed-size storage.

Multidimensional Arrays

The multidimensional extension of the maximum subarray problem to two dimensions, known as the maximum subrectangle sum problem, requires identifying a contiguous submatrix within an m×nm \times n matrix of real numbers that maximizes the sum of its elements. This generalization arises naturally in applications such as image processing, where it helps detect regions of maximum intensity or pattern significance in pixel arrays. The problem was first systematically explored as a two-dimensional counterpart to the one-dimensional case. An efficient algorithm for this problem runs in O(mn2)O(mn^2) time (or O(n3)O(n^3) for square matrices), extending Kadane's dynamic programming approach from one dimension. The method iterates over all possible left and right column pairs (from 1 to nn), computes a temporary one-dimensional array of size mm by summing the elements between the fixed columns for each row, and then applies Kadane's algorithm to this temporary array to find the maximum contiguous sum, which corresponds to the optimal top and bottom rows for that column range. The global maximum across all pairs yields the desired subrectangle sum. This nested structure leverages the linear-time efficiency of Kadane's algorithm while bounding the outer loops by O(n2)O(n^2). The following pseudocode outlines the core procedure, assuming a matrix A[1..m][1..n]A[1..m][1..n] and 1-based indexing:

max_sum = -∞ for l = 1 to n do initialize temp[1..m] = 0 for r = l to n do for i = 1 to m do temp[i] = temp[i] + A[i][r] end for current_max = Kadane(temp) // Apply 1D Kadane's to find max subarray sum in temp if current_max > max_sum then max_sum = current_max end if end for end for

max_sum = -∞ for l = 1 to n do initialize temp[1..m] = 0 for r = l to n do for i = 1 to m do temp[i] = temp[i] + A[i][r] end for current_max = Kadane(temp) // Apply 1D Kadane's to find max subarray sum in temp if current_max > max_sum then max_sum = current_max end if end for end for

Here, the inner accumulation updates the temporary array incrementally to avoid redundant summation. The space complexity is O(m)O(m) for the temporary array, making it practical for moderate-sized inputs. For illustration, consider the following 4×4 matrix: [0−2−7092−62−41−41−180−2]\begin{bmatrix} 0 & -2 & -7 & 0 \\ 9 & 2 & -6 & 2 \\ -4 & 1 & -4 & 1 \\ -1 & 8 & 0 & -2 \\ \end{bmatrix}
Add your contribution
Related Hubs
User Avatar
No comments yet.