Maximum subarray (Kadane)

Challenge

Implement:

long long max_subarray(const int *a, int n);

Return the maximum sum of a non-empty contiguous subarray (Kadane's algorithm). n >= 1.

Input format

Array a, count n>=1.

Output format

Maximum contiguous sum.

Constraints

Handle all-negative arrays (answer is the largest element).

Starter code

#include <stddef.h>
/* Maximum sum of a non-empty contiguous subarray (Kadane). n>=1. */
long long max_subarray(const int *a,int n){ (void)a;(void)n; return 0; }

Common mistakes

Resetting the running sum to 0 (wrong for all-negative inputs) instead of starting a fresh subarray.

Edge cases to handle

Single element -> that element.

Background lessons

• LIS & Kadane's algorithm