Maximum Subarray in c#

Programming C#
1

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

  1. 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.

  2. 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 of nums[i] or the sum of max_current + nums[i]. This step decides whether to start a new subarray at nums[i] or to continue adding to the existing subarray.
      • If max_current exceeds max_global, we update max_global.

  3. Return the Result:

    • After iterating through the array, max_global contains the maximum sum of the contiguous subarray.

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

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!