Maximum Subarray

Given an array of integers, find the contiguous subarray with the largest sum. Brute-force over all subarrays is O(n^2).

Function signature

func MaxSubArray(nums []int) int

Inputs / outputs

• nums: non-empty array of integers.
• Return: maximum subarray sum.

Example

nums = [-2,1,-3,4,-1,2,1,-5,4]
Best subarray: [4,-1,2,1] -> 6
Output: 6

Constraints

• 1 <= len(nums) <= 100_000

Core idea (near-solution)

Kadane's algorithm: track the best subarray ending at each position.

Invariant: cur is the best sum of a subarray that must end at i.

Algorithm (step-by-step)

1. Initialize cur = best = nums[0].
2. For each i from 1..:
   • cur = max(nums[i], cur + nums[i]).
   • best = max(best, cur).
3. Return best.

Correctness sketch

• Invariant: cur is the best sum of a subarray that must end at i.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
nums = [-2,1,-3,4,-1,2,1,-5,4]
Best subarray: [4,-1,2,1] -> 6
Output: 6

Walk:
- cur=-2 best=-2
- val=1 -> cur=1 best=1; val=-3 -> cur=-2
- val=4 -> cur=4 best=4; val=-1 -> cur=3
- val=2 -> cur=5; val=1 -> cur=6 best=6

Pitfalls to avoid

• Initializing cur to 0 (fails for all-negative arrays).
• Confusing subarray (contiguous) with subsequence.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Use ints; values fit within constraints.