How can the method also return where the best block starts and ends?

Java has no multiple return values, so wrap the three numbers in a record: record Result(int sum, int start, int end) {}. Loop with an index, keep runStart, and when current + n < n restart with current = n and runStart = i. Each time current exceeds the best so far, store it together with runStart and i. The generated toString prints Result[sum=12, start=2, end=5] for the first example and Result[sum=-3, start=1, end=1] for the all-negative one.

Can the int total overflow, and how do I guard against it?

Yes, and silently. Past 2,147,483,647 an int wraps to a negative value, and Kadane quietly drops the block it should keep: given {2_000_000_000, 2_000_000_000} the int method returns 2000000000, because current + n wrapped. Make best and current long (each int element widens by itself) and the result becomes 4000000000. To crash rather than wrap, use Math.addExact, which throws java.lang.ArithmeticException: integer overflow.

What happens with an empty array or null?

Every version ends up reading nums[0], so new int[0] throws java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0, and a null reference throws NullPointerException. When empty input is legitimate, test nums == null || nums.length == 0 up front and return OptionalInt.empty(), or throw IllegalArgumentException, so callers cannot mistake missing input for a real total.

Does the code work on a List instead of an int[]?

Not as written, since maxSubarray takes int[]. Either convert once with list.stream().mapToInt(Integer::intValue).toArray() and keep the primitive loop, or change the parameter to List and write for (int n : list), which unboxes each element. Both return the same answer; the array version skips the per-element unboxing. If you keep values boxed, never compare two Integer objects with ==, which compares references, not numbers.

How does the answer change if an empty block counts?

Zero becomes the floor. Initialise best and current to 0 instead of nums[0], and clamp with current = Math.max(0, current + n) so a sinking total resets to nothing. For {-7, -3, -8, -5} the method then returns 0 rather than -3; for {4, -6, 3, 5, -2, 6, -9, 1} the answer stays 12.

Maximum Subarray in Java: Brute Force to Kadane's Algorithm

Q: Can the int total overflow, and how do I guard against it?

Yes, and silently. Past 2,147,483,647 an int wraps to a negative value, and Kadane quietly drops the block it should keep: given {2_000_000_000, 2_000_000_000} the int method returns 2000000000, because current + n wrapped. Make best and current long (each int element widens by itself) and the result becomes 4000000000. To crash rather than wrap, use Math.addExact, which throws java.lang.ArithmeticException: integer overflow.

Q: What happens with an empty array or null?

Every version ends up reading nums[0], so new int[0] throws java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0, and a null reference throws NullPointerException. When empty input is legitimate, test nums == null || nums.length == 0 up front and return OptionalInt.empty(), or throw IllegalArgumentException, so callers cannot mistake missing input for a real total.

Q: Does the code work on a List instead of an int[]?

Not as written, since maxSubarray takes int[]. Either convert once with list.stream().mapToInt(Integer::intValue).toArray() and keep the primitive loop, or change the parameter to List and write for (int n : list), which unboxes each element. Both return the same answer; the array version skips the per-element unboxing. If you keep values boxed, never compare two Integer objects with ==, which compares references, not numbers.

Q: How does the answer change if an empty block counts?

Zero becomes the floor. Initialise best and current to 0 instead of nums[0], and clamp with current = Math.max(0, current + n) so a sinking total resets to nothing. For {-7, -3, -8, -5} the method then returns 0 rather than -3; for {4, -6, 3, 5, -2, 6, -9, 1} the answer stays 12.

max_subarray.java

Java 25.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.