Maximum Subarray Sum

Problem Statement

Given an integer array nums, find the contiguous subarray that has the largest sum and return that sum. This is the classic Kadane problem. If asked, mention how to also recover the start and end indices of the best subarray.

Examples

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

Output: 6

Explanation: The subarray [4,-1,2,1] gives the maximum sum 6.

Input: nums = [1]

Output: 1

Explanation: A single element itself is the best subarray.

Custom Notes

Contiguous is the real keyword.
Negative running prefix hurts every future extension.
Initialize answer with nums[0], not 0, to handle all-negative arrays.
Memory hook: extend good prefix, drop bad prefix.
If the interviewer asks for the subarray, track tentative start and final boundaries.

Brute Force Approach : TC: SC:

1 / 3

Algorithm: Start every subarray and extend it to the right while tracking sum.

Pseudo:

For each start index i, set runningSum = 0.
For each end index j from i to n - 1, add nums[j] into runningSum.
Update the best answer with runningSum.

Time: O(n^2)

Space: O(1)

Why mention it: It is simple and still better than checking each subarray sum from scratch in O(n^3).

Better Approach : TC: SC:

2 / 3

Algorithm: Use DP thinking where best subarray ending at i is either nums[i] alone or nums[i] plus best ending at i - 1.

Pseudo:

Let dp[i] be the best subarray sum ending at i.
dp[i] = max(nums[i], nums[i] + dp[i - 1]).
Track the maximum value over all dp[i].

Time: O(n)

Space: O(n)

Interview line: This transitions directly into Kadane when you optimize away the DP array.

Optimal Approach : TC: SC:

3 / 3

Algorithm: Maintain currentSum for the best subarray ending here and bestSum for the global answer.

Pseudo:

Initialize currentSum = 0 and bestSum = nums[0].
For each number x, add x to currentSum.
Update bestSum = max(bestSum, currentSum).
If currentSum becomes negative, reset currentSum to 0.

Time: O(n)

Space: O(1)

Key insight: A negative prefix can only reduce the sum of any future subarray, so we drop it.

PCode

1 / 3

bestSum = negative infinity

FOR start from 0 to n - 1
    runningSum = 0
    FOR end from start to n - 1
        runningSum = runningSum + nums[end]
        bestSum = max(bestSum, runningSum)

RETURN bestSum

PCode

2 / 3

dp[0] = nums[0]
bestSum = dp[0]

FOR i from 1 to n - 1
    dp[i] = max(nums[i], nums[i] + dp[i - 1])
    bestSum = max(bestSum, dp[i])

RETURN bestSum

PCode

3 / 3

currentSum = 0
bestSum = nums[0]

FOR each value x in nums
    currentSum = currentSum + x
    bestSum = max(bestSum, currentSum)
    IF currentSum < 0
        currentSum = 0

RETURN bestSum