@meta
title: Maximum Subarray Sum
questionNo: 4
totalQuestions: 191
sheetLabel: Striver SDE Sheet
sourceLabel: TakeUForward
@endmeta

@page
tag: A
pageNo: 1 / 1
totalPages: 1
@endpage

@section
region: full
title: Problem Statement
content:
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.
@endsection

@section
region: left
title: Examples
content:
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.
@endsection

@section
region: right
title: Custom Notes
content:
- 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.
@endsection

@section
region: full
title: Brute Force Approach : TC: SC:
badge: 1 / 3
content:
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).
@endsection

@section
region: full
title: Better Approach : TC: SC:
badge: 2 / 3
content:
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.
@endsection

@section
region: full
title: Optimal Approach : TC: SC:
badge: 3 / 3
content:
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.
@endsection

@section
region: grid
title: PCode
badge: 1 / 3
codeLang: pseudo
content:
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
@endsection

@section
region: grid
title: PCode
badge: 2 / 3
codeLang: pseudo
content:
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
@endsection

@section
region: grid
title: PCode
badge: 3 / 3
codeLang: pseudo
content:
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
@endsection