Crack the Backend

Problem Statement

You are given an integer array nums. Find the contiguous subarray (containing at least one number) that has the largest sum, and return that sum.

A subarray is a contiguous part of the array (consecutive indices).
The array may contain negative numbers; the maximum sum might come from a segment that does not include the whole array.
If the array has only one element, return that element.
Follow-up: If you are asked to return the left and right indices of the maximum subarray, the same idea applies while tracking indices.

Key Observations

At each position i, the best subarray ending at i either extends the best subarray ending at i-1 (if that sum is positive) or starts fresh at i (if extending would hurt).
If the running sum ever becomes negative, discarding it and starting from the next element is never worse than carrying it forward — a negative prefix only reduces any future extension.
So we only need one pass: maintain "max sum of a subarray ending at the current index" and a global "best sum seen so far."
This is Kadane's algorithm: linear time and constant space.

Approach

High-level: For each index i, compute the maximum sum of any subarray ending at i. That value is either nums[i] alone (start fresh) or nums[i] + max(0, runningSum) (extend the previous segment only if it helps). Track the global maximum over all such ending sums.

Steps:

Initialize cur = nums[0] (best sum ending at index 0) and best = nums[0] (global best).
For i from 1 to n-1: set cur = max(nums[i], cur + nums[i]) (extend or restart), then best = max(best, cur).
Return best.

Implementation

Java

public int maxSubArray(int[] nums) {
    int cur = nums[0], best = nums[0];

    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        best = Math.max(best, cur);
    }

    return best;
}

Test Cases

Example 1

Input

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

Expected

6

Explanation

The contiguous subarray [4,-1,2,1] has sum 6; no other subarray has a larger sum.

Complexity Analysis

Time: O(n) — single pass over the array.
Space: O(1) — only two variables (current ending sum and global best).

Follow-ups

Return the left and right indices of the maximum subarray (track indices when you update best).
Maximum Sum Circular Subarray: the array is circular; the maximum sum might wrap around. Consider both the non-circular maximum and the circular case (total sum minus minimum subarray sum).
What if you are allowed to delete at most one element from the array? (Hint: track max sum with one deletion.)