To find the maximum sum of a contiguous subarray within a one-dimensional numeric array, you can use Kadane’s algorithm. This algorithm runs in linear time and is very efficient. Below is a C# implementation along with an explanation of how it works.
C# Implementation
public class Solution {
public int MaxSubArray(int[] nums) {
// Initialize max_current and max_global to the first element
int max_current = nums[0];
int max_global = nums[0];
// Iterate through the array starting from the second element
for (int i = 1; i < nums.Length; i++) {
// Update max_current to the maximum of the current element
// or the current element plus the previous max_current
max_current = Math.Max(nums[i], max_current + nums[i]);
// Update max_global if max_current is greater
if (max_current > max_global) {
max_global = max_current;
}
}
return max_global;
}
}
Explanation
-
Initialization:
- We start by initializing two variables:
max_current
: This keeps track of the maximum sum of the subarray that ends at the current position.max_global
: This records the overall maximum found so far.
- We start by initializing two variables:
-
Iterating Through the Array:
- We loop through the array starting from the second element (index 1). For each element
nums[i]
, we do the following:- Calculate
max_current
as the maximum ofnums[i]
or the sum ofmax_current + nums[i]
. This step decides whether to start a new subarray atnums[i]
or to continue adding to the existing subarray. - If
max_current
exceedsmax_global
, we updatemax_global
.
- Calculate
- We loop through the array starting from the second element (index 1). For each element
-
Return the Result:
- After iterating through the array,
max_global
contains the maximum sum of the contiguous subarray.
- After iterating through the array,
Example Walkthrough
Consider the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]
.
-
Initialization:
max_current = -2
,max_global = -2
.
-
Iteration:
- For
1
:max_current = max(1, -2 + 1) = 1
→max_global = 1
- For
-3
:max_current = max(-3, 1 - 3) = -2
→max_global = 1
- For
4
:max_current = max(4, -2 + 4) = 4
→max_global = 4
- For
-1
:max_current = max(-1, 4 - 1) = 3
- For
2
:max_current = max(2, 3 + 2) = 5
→max_global = 5
- For
1
:max_current = max(1, 5 + 1) = 6
→max_global = 6
- For
-5
:max_current = max(-5, 6 - 5) = 1
- For
4
:max_current = max(4, 1 + 4) = 5
- For
After completing the loop, the maximum sum of the contiguous subarray is 6
, which corresponds to the subarray [4, -1, 2, 1]
.
Complexity
- Time Complexity: O(n), where n is the number of elements in the array, because we traverse the array once.
- Space Complexity: O(1), as we are using a constant amount of space for the variables.
This makes Kadane’s algorithm a very efficient way to solve the maximum subarray problem!