Introduction

The Maximum Subarray problem involves finding the contiguous subarray with the largest possible sum.

Given an integer array arr[], the task is to find:

  • the contiguous subarray having maximum sum
  • and return that maximum sum

This is one of the most important array problems and introduces the famous:

 Kadane’s Algorithm

This problem helps in understanding:

  • dynamic programming intuition
  • running sum optimization
  • greedy decisions
  • subarray processing

Example

Input: arr[] = [-2,1,-3,4,-1,2,1,-5,4]Output: 6Explanation:
Subarray:
[4,-1,2,1]
Sum = 6
This is the maximum possible subarray sum.

Input: arr[] = [5,4,-1,7,8]
Output: 23
Explanation:
Entire array forms the maximum subarray.
5 + 4 + (-1) + 7 + 8 = 23

Constraints

 1 <= n <= 10^5 -10^4 <= arr[i] <= 10^4

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all possible subarrays
  2. Calculate the sum of every subarray
  3. Track the maximum sum

This approach is easy to understand but repeated subarray calculations increase time complexity.

Steps

  1. Traverse all starting indices.
  2. Generate subarrays from each index.
  3. Calculate current subarray sum.
  4. Update maximum sum.
  5. Return final maximum sum.

Dry Run

Input Array:[-2,1,-3,4,-1,2,1,-5,4]

Start from -2:
Current Sum = -2
Maximum Sum = -2

Add 1:
Current Sum = -1
Maximum Sum = -1
Continue traversal...

Start from 4:
Subarray:
[4,-1,2,1]
Current Sum = 6
Maximum Sum = 6

Final Result:
6

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
All possible subarrays are generated and processed.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Kadane’s Algorithm)

Explanation

Kadane’s Algorithm efficiently finds the maximum subarray sum using a running sum approach.

The idea is:

  1. Maintain:
    • current sum
    • maximum sum
  2. If current sum becomes negative:
    • discard it
    • start new subarray

This works because:

  • a negative running sum can never help future subarrays.

Steps

  1. Initialize:
    • current_sum = 0
    • max_sum = smallest value
  2. Traverse the array.
  3. Add current element to current_sum.
  4. Update maximum sum.
  5. If current_sum becomes negative:
    • reset it to 0
  6. Return maximum sum.

Dry Run

Input Array:[-2,1,-3,4,-1,2,1,-5,4]

Initially:
current_sum = 0
max_sum = -∞

Traverse -2:
current_sum = -2
max_sum = -2
current_sum becomes negative
Reset current_sum = 0

Traverse 1:
current_sum = 1
max_sum = 1

Traverse -3:
current_sum = -2
Reset current_sum = 0

Traverse 4:
current_sum = 4
max_sum = 4

Traverse -1:
current_sum = 3

Traverse 2:
current_sum = 5
max_sum = 5

Traverse 1:
current_sum = 6
max_sum = 6

Final Result:
6

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element is processed exactly once.

Space Complexity: O(1)
Explanation:
Only variables are used for tracking sums.

Edge Cases

  1. Array contains all negative numbers
  2. Array contains all positive numbers
  3. Array contains zeros
  4. Maximum subarray is entire array
  5. Maximum subarray contains one element

Why This Problem is Important

This problem helps in understanding:

  1. Kadane’s Algorithm
  2. Dynamic programming intuition
  3. Running sum optimization
  4. Greedy decisions
  5. Subarray processing

It is one of the most important array interview problems.

Real-World Applications

Maximum subarray concepts are used in:

  1. Stock market analysis
  2. Profit optimization systems
  3. Signal processing
  4. Financial analytics
  5. Data trend analysis

Common Mistakes

  1. Incorrect sum reset logic
  2. Forgetting all-negative arrays
  3. Updating maximum sum incorrectly
  4. Resetting sum too early

Interview Tips

Interviewers often expect:

  1. Kadane’s Algorithm
  2. O(n) solution
  3. Proper running sum explanation

Always explain why negative running sums are discarded.

Related Questions

  1. Maximum Product Subarray
  2. Circular Subarray Sum
  3. Best Time to Buy and Sell Stock
  4. Pair Sum
  5. Longest Subarray

Final Takeaway

The Maximum Subarray problem is a fundamental Kadane’s Algorithm problem that teaches running sum optimization and greedy decision-making techniques. Understanding this problem builds a strong foundation for advanced dynamic programming and subarray interview problems.