How do I return the start and end indices of the best run as well?

Return a tuple: change the signature to (int Sum, int Start, int End) MaxSubarray(int[] nums). Loop with an index, keep runStart, and when current + n < n restart with current = n and runStart = i. Each time current beats the best so far, store (current, runStart, i). The first example gives (12, 2, 5) and the all-negative one (-3, 1, 1); callers can deconstruct it with var (sum, start, end) = ....

Can the int sum overflow, and how do I catch it?

Yes, and by default it wraps silently: C# arithmetic is unchecked unless the project sets or the code is inside a checked block. On { 2_000_000_000, 2_000_000_000 } the int version returns 2000000000 because current + n wrapped negative. Declare best and current as long (each int element widens on its own) and the result is 4000000000. To fail loudly instead, wrap the additions in checked(...), which throws System.OverflowException.

What happens with an empty array or null?

Every version reads nums[0] first, so new int[0] throws System.IndexOutOfRangeException and null throws System.NullReferenceException. If empty input is legitimate in your code, test nums is null || nums.Length == 0 up front and return int? (null for no run) or throw ArgumentException, so a missing input is never confused with a real sum.

Can I write Kadane with LINQ instead of a loop?

You can fold with Aggregate: nums.Aggregate((best: nums[0], current: 0), (acc, n) => { var cur = Math.Max(n, acc.current + n); return (Math.Max(acc.best, cur), cur); }).best. It is the same algorithm with a tuple as the accumulator, but harder to read and slower than the foreach, which stays on the stack with two locals. nums.Max() alone is wrong: it returns the largest single element, which only matches the answer when every value is negative.

Does the method work on a List or a Span instead of an int[]?

Not as declared, since the parameter is int[]. foreach over a List compiles unchanged, so you can retype the parameter to IReadOnlyList or IEnumerable (then take best from the first element rather than nums[0]). For slices without copying, take a ReadOnlySpan and call it with nums.AsSpan(2, 4); the loop body is identical.

Maximum Subarray in C#: Brute Force to Kadane's Algorithm

Q: Can the int sum overflow, and how do I catch it?

Yes, and by default it wraps silently: C# arithmetic is unchecked unless the project sets or the code is inside a checked block. On { 2_000_000_000, 2_000_000_000 } the int version returns 2000000000 because current + n wrapped negative. Declare best and current as long (each int element widens on its own) and the result is 4000000000. To fail loudly instead, wrap the additions in checked(...), which throws System.OverflowException.

Q: What happens with an empty array or null?

Every version reads nums[0] first, so new int[0] throws System.IndexOutOfRangeException and null throws System.NullReferenceException. If empty input is legitimate in your code, test nums is null || nums.Length == 0 up front and return int? (null for no run) or throw ArgumentException, so a missing input is never confused with a real sum.

Q: Can I write Kadane with LINQ instead of a loop?

You can fold with Aggregate: nums.Aggregate((best: nums[0], current: 0), (acc, n) => { var cur = Math.Max(n, acc.current + n); return (Math.Max(acc.best, cur), cur); }).best. It is the same algorithm with a tuple as the accumulator, but harder to read and slower than the foreach, which stays on the stack with two locals. nums.Max() alone is wrong: it returns the largest single element, which only matches the answer when every value is negative.

max_subarray.cs

C# 10.0

Not run yet

+ 7 hidden

Input

nums = [4, -6, 3, 5, -2, 6, -9, 1]

Expected

The run [3, 5, -2, 6] sums to 12. The -2 is worth carrying because the 6 after it more than pays it back.