Subarray Problems

A coffee shop owner tracks daily earnings:

[100, -50, 200, -30, 150, -20, 300]

Some days are great, some are bad.

But the owner isn’t interested in just one day.
He wants to know:

“Which continuous stretch of days gave me the highest profit?”

Not random days.
Not scattered choices.
Only continuous days.

That’s exactly what a subarray is.

What is a Subarray?

A subarray is a continuous part of an array.

Important:

• Must be continuous
• Order matters

Brute Force Approach (Checking Every Possibility)

You try every possible subarray and calculate the sum.

Problem:

• Time Complexity = O(n³) (very slow)

Kadane’s Algorithm (The Smart Insight)

Instead of checking everything, we think smart:

“If the current sum becomes negative, drop it!”

Because a negative sum will only reduce future profit.

Concept - Maximum Subarray Sum

Technical Example:

Input:

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

Output:

6  → subarray [4, -1, 2, 1]

Real-Life Insight:

• Ignore bad streaks (loss days)
• Focus on profitable continuous period

This is optimization thinking

Sliding Window (Fixed Size Subarrays)

Sometimes interviewer asks:

“Find maximum sum of subarray of size k”

Example:

Concept - Window Moves Forward

Time Complexity = O(n)

Real-Life Example:

Finding the best 3-day sales period without recalculating everything.

Interviewers don’t say “subarray problem”.

They say things like:

• “Continuous segment”
• “Maximum sum”
• “Longest length”
• “Fixed size window”

All are hints toward subarray techniques