Maximum Subarray: the idea to remember.

The core insight

At each value, choose between starting a new segment and extending the best segment ending just before it.

Why it works

Any segment ending at i either starts at i or extends a segment ending at i minus one; keeping only the best such suffix is sufficient.

The mistake to avoid

Initialize from the first value so an all negative array does not incorrectly return zero.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

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

Make the next connection