Coding · Easy · Free
Maximum subarray sum with at least one element (Kadane)
CodingAlgorithmsFresher
Approach
- Track current sum; reset to 0 when it goes negative.
- Update global max after each step.
Java Solution
Java
public int maxSubArray(int[] nums) {
int best = nums[0], cur = 0;
for (int x : nums) {
cur = Math.max(x, cur + x);
best = Math.max(best, cur);
}
return best;
}| Complexity | |
|---|---|
| Time | O(n) |
| Space | O(1) |
Interview tip: Variant: circular array or limit subarray length k.