C# Program to Find Maximum Subarray Sum

Use Kadane's algorithm in C# by iterating through the array, updating current and maximum sums with currentSum = Math.Max(num, currentSum + num) and maxSum = Math.Max(maxSum, currentSum) to find the maximum subarray sum.

Examples

Input[-2,1,-3,4,-1,2,1,-5,4]

Output6

Input[1,2,3,4,5]

Output15

Input[-1,-2,-3,-4]

Output-1

How to Think About It

To find the maximum sum of a continuous subarray, move through the array while keeping track of the current sum of the subarray. If adding the next number makes the sum smaller than the number itself, start a new subarray from that number. Keep updating the maximum sum found so far.

Algorithm

1

Initialize two variables: currentSum and maxSum with the first element of the array.

2

Loop through the array starting from the second element.

3

For each element, update currentSum to be the maximum of the element itself or currentSum plus the element.

4

Update maxSum if currentSum is greater than maxSum.

5

After the loop ends, return maxSum as the maximum subarray sum.

Code

csharp

using System;
class Program {
    static int MaxSubArraySum(int[] nums) {
        int currentSum = nums[0], maxSum = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            maxSum = Math.Max(maxSum, currentSum);
        }
        return maxSum;
    }
    static void Main() {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Console.WriteLine(MaxSubArraySum(arr));
    }
}

Dry Run

Let's trace the example array [-2,1,-3,4,-1,2,1,-5,4] through the code

1

Initialize

currentSum = -2, maxSum = -2

2

i=1, num=1

currentSum = max(1, -2+1) = 1; maxSum = max(-2,1) = 1

3

i=2, num=-3

currentSum = max(-3, 1-3) = -2; maxSum = max(1,-2) = 1

4

i=3, num=4

currentSum = max(4, -2+4) = 4; maxSum = max(1,4) = 4

5

i=4, num=-1

currentSum = max(-1, 4-1) = 3; maxSum = max(4,3) = 4

6

i=5, num=2

currentSum = max(2, 3+2) = 5; maxSum = max(4,5) = 5

7

i=6, num=1

currentSum = max(1, 5+1) = 6; maxSum = max(5,6) = 6

8

i=7, num=-5

currentSum = max(-5, 6-5) = 1; maxSum = max(6,1) = 6

9

i=8, num=4

currentSum = max(4, 1+4) = 5; maxSum = max(6,5) = 6

Index	Num	CurrentSum	MaxSum
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

Why This Works

Step 1: Start with first element

Initialize currentSum and maxSum with the first number to have a starting point for comparison.

Step 2: Update current sum

At each step, decide if starting fresh from the current number is better than continuing the previous subarray by using Math.Max(num, currentSum + num).

Step 3: Track maximum sum

Keep updating maxSum to remember the highest sum found so far, ensuring the final answer is the largest subarray sum.

Alternative Approaches

Brute Force

csharp

using System;
class Program {
    static int MaxSubArraySum(int[] nums) {
        int maxSum = int.MinValue;
        for (int i = 0; i < nums.Length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.Length; j++) {
                currentSum += nums[j];
                if (currentSum > maxSum) maxSum = currentSum;
            }
        }
        return maxSum;
    }
    static void Main() {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Console.WriteLine(MaxSubArraySum(arr));
    }
}

Simple but slow approach with O(n^2) time complexity, not efficient for large arrays.

Divide and Conquer

csharp

using System;
class Program {
    static int MaxCrossingSum(int[] arr, int left, int mid, int right) {
        int sum = 0, leftSum = int.MinValue;
        for (int i = mid; i >= left; i--) {
            sum += arr[i];
            if (sum > leftSum) leftSum = sum;
        }
        sum = 0; int rightSum = int.MinValue;
        for (int i = mid + 1; i <= right; i++) {
            sum += arr[i];
            if (sum > rightSum) rightSum = sum;
        }
        return leftSum + rightSum;
    }
    static int MaxSubArraySum(int[] arr, int left, int right) {
        if (left == right) return arr[left];
        int mid = (left + right) / 2;
        return Math.Max(Math.Max(MaxSubArraySum(arr, left, mid), MaxSubArraySum(arr, mid + 1, right)), MaxCrossingSum(arr, left, mid, right));
    }
    static void Main() {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Console.WriteLine(MaxSubArraySum(arr, 0, arr.Length - 1));
    }
}

Uses recursion and divide-and-conquer with O(n log n) time, more complex but faster than brute force.

Complexity: O(n) time, O(1) space

Time Complexity

The algorithm loops through the array once, so the time complexity is O(n), where n is the number of elements.

Space Complexity

Only a few variables are used to track sums, so space complexity is O(1), constant extra space.

Which Approach is Fastest?

Kadane's algorithm is fastest with O(n) time, compared to brute force O(n^2) and divide-and-conquer O(n log n).

Approach	Time	Space	Best For
Kadane's Algorithm	O(n)	O(1)	Large arrays, efficient
Brute Force	O(n^2)	O(1)	Small arrays, simple implementation
Divide and Conquer	O(n log n)	O(log n)	Medium arrays, recursive approach