Kadane's Algorithm Maximum Subarray in DSA C - Deep Dive

Overview - Kadane's Algorithm Maximum Subarray

What is it?

Kadane's Algorithm is a method to find the largest sum of a continuous part of an array of numbers. It looks for the subarray (a slice of the array) that adds up to the highest value. This algorithm works by scanning the array once, keeping track of the best sum found so far. It is simple, fast, and uses only a little extra memory.

Why it matters

Without Kadane's Algorithm, finding the maximum sum subarray would take much longer, especially for big arrays. This would slow down programs that need to analyze data quickly, like stock price changes or temperature readings. Kadane's Algorithm makes these tasks efficient and practical, saving time and computing power.

Where it fits

Before learning Kadane's Algorithm, you should understand arrays and basic loops. After this, you can explore related topics like divide and conquer methods for maximum subarray, dynamic programming, and problems involving subarray sums or intervals.

Mental Model

Core Idea

Keep track of the current sum and reset it when it becomes negative, while remembering the highest sum found so far.

Think of it like...

Imagine walking along a path where each step adds or subtracts energy. If your energy drops below zero, you start fresh from the next step, but you always remember the highest energy level you reached.

Array:  [ -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 ]

Tracking:
Current Sum: 0 -> 1 -> -2 -> 4 -> 3 -> 5 -> 6 -> 1 -> 5
Max Sum:     0 -> 1 -> 1 -> 4 -> 4 -> 5 -> 6 -> 6 -> 6

Build-Up - 7 Steps

1

Foundation

Understanding the Maximum Subarray Problem

Concept: What does it mean to find the maximum sum of a continuous subarray?

Given an array of numbers, the goal is to find a slice of the array where the sum of its elements is as large as possible. For example, in [1, -2, 3, 4], the subarray [3, 4] sums to 7, which is the maximum possible.

Result

You understand the problem: find the continuous part of the array with the highest sum.

Understanding the problem clearly is the first step to solving it efficiently.

2

Foundation

Brute Force Approach to Maximum Subarray

Concept: Try every possible subarray and calculate their sums to find the maximum.

Check all subarrays by using two loops: one for the start index and one for the end index. Sum each subarray and keep track of the largest sum found. This method works but is slow for large arrays because it checks many subarrays.

Result

Correct maximum sum but with time complexity O(n^2) or worse.

Brute force shows the problem is solvable but inefficient, motivating a better approach.

3

Intermediate

Key Insight: Reset When Sum Drops Below Zero

🤔Before reading on: do you think keeping a negative sum helps or hurts finding the maximum subarray? Commit to your answer.

Concept: If the current sum becomes negative, it cannot help increase future sums, so reset it to zero.

While scanning the array, add each element to a running sum. If this sum becomes negative, reset it to zero because starting fresh from the next element is better. Keep track of the maximum sum seen so far.

Result

You can find the maximum sum in one pass with O(n) time.

Knowing when to reset the sum avoids wasting effort on subarrays that reduce the total.

4

Intermediate

Implementing Kadane's Algorithm in C

🤔Before reading on: do you think Kadane's Algorithm needs extra memory proportional to array size? Commit to your answer.

Concept: Kadane's Algorithm uses two variables to track current and maximum sums, scanning the array once.

Code example: #include int maxSubArray(int* nums, int numsSize) { int max_so_far = nums[0]; int current_max = 0; for (int i = 0; i < numsSize; i++) { current_max += nums[i]; if (current_max > max_so_far) { max_so_far = current_max; } if (current_max < 0) { current_max = 0; } } return max_so_far; } int main() { int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; int size = sizeof(arr) / sizeof(arr[0]); int max_sum = maxSubArray(arr, size); printf("Maximum subarray sum is %d\n", max_sum); return 0; }

Result

Output: Maximum subarray sum is 6

Kadane's Algorithm is efficient and uses constant extra space, making it practical for large data.

5

Intermediate

Handling All Negative Numbers Correctly

🤔Before reading on: do you think Kadane's Algorithm works as is if all numbers are negative? Commit to your answer.

Concept: Kadane's Algorithm needs a small change to handle arrays where all numbers are negative.

If all numbers are negative, resetting current sum to zero loses the maximum negative number. To fix this, initialize max_so_far to the first element and current_max to zero, but update max_so_far even if current_max is reset. Alternatively, track the maximum element separately.

Result

Correct maximum sum even when all elements are negative.

Handling edge cases ensures the algorithm works correctly in all scenarios.

6

Advanced

Extending Kadane's Algorithm to Find Subarray Indices

🤔Before reading on: do you think Kadane's Algorithm can tell which subarray gives the max sum? Commit to your answer.

Concept: By tracking start and end indices during the scan, we can find the exact subarray with the maximum sum.

Add variables to remember the start of the current subarray and update the best start and end indices when a new max is found. Reset start index when current sum resets. Example code snippet: int maxSubArrayWithIndices(int* nums, int numsSize, int* start, int* end) { int max_so_far = nums[0]; int current_max = 0; int temp_start = 0; *start = 0; *end = 0; for (int i = 0; i < numsSize; i++) { current_max += nums[i]; if (current_max > max_so_far) { max_so_far = current_max; *start = temp_start; *end = i; } if (current_max < 0) { current_max = 0; temp_start = i + 1; } } return max_so_far; }

Result

You get both the maximum sum and the exact subarray boundaries.

Knowing the subarray itself is often more useful than just the sum.

7

Expert

Kadane's Algorithm and Dynamic Programming Connection

🤔Before reading on: do you think Kadane's Algorithm is a form of dynamic programming? Commit to your answer.

Concept: Kadane's Algorithm is a simple dynamic programming approach that builds the solution using previous results.

At each position, the algorithm decides whether to add the current element to the previous subarray or start fresh. This decision uses the optimal solution of the previous step, which is the essence of dynamic programming. The recurrence is: current_max = max(nums[i], current_max + nums[i]) max_so_far = max(max_so_far, current_max) This shows Kadane's Algorithm is a bottom-up dynamic programming solution with O(n) time and O(1) space.

Result

Understanding Kadane's Algorithm as dynamic programming helps apply similar patterns to other problems.

Recognizing the dynamic programming nature reveals why Kadane's Algorithm is both simple and powerful.

Under the Hood

Kadane's Algorithm works by iterating through the array once, maintaining two variables: current_max and max_so_far. current_max accumulates the sum of the current subarray. If current_max drops below zero, it resets to zero, effectively discarding any negative sum that would reduce future totals. max_so_far keeps track of the highest sum found so far. This process ensures the algorithm finds the maximum sum subarray in linear time without extra memory.

Why designed this way?

The algorithm was designed to improve on the brute force O(n^2) approach by using a greedy strategy combined with dynamic programming principles. Resetting the sum when negative avoids unnecessary calculations. This design balances simplicity, speed, and minimal memory use, making it ideal for large datasets and real-time applications.

Start -> [Iterate array elements]
  ↓
[Add current element to current_max]
  ↓
[Is current_max < 0?] -> Yes -> current_max = 0 (reset)
  ↓ No
[Update max_so_far if current_max > max_so_far]
  ↓
Repeat until end of array
  ↓
Return max_so_far

Myth Busters - 4 Common Misconceptions

Quick: Does Kadane's Algorithm always find the maximum subarray even if all numbers are negative? Commit yes or no.

Common Belief: Kadane's Algorithm works perfectly on any array, including all negative numbers, without changes.

Reality: The classic Kadane's Algorithm resets current sum to zero, which fails if all numbers are negative. It needs adjustment to handle this case correctly.

Why it matters: Without this fix, the algorithm returns zero instead of the largest negative number, giving wrong results in all-negative arrays.

Quick: Does Kadane's Algorithm require extra memory proportional to the array size? Commit yes or no.

Common Belief: Kadane's Algorithm needs extra arrays or memory to store sums or subarrays.

Reality: Kadane's Algorithm uses only a few variables and runs in constant extra space O(1).

Why it matters: Thinking it needs extra memory may discourage using it in memory-sensitive applications.

Quick: Is Kadane's Algorithm a brute force method? Commit yes or no.

Common Belief: Kadane's Algorithm tries all subarrays like brute force but faster.

Reality: Kadane's Algorithm never checks all subarrays explicitly; it uses a clever running sum and resets to find the max efficiently.

Why it matters: Misunderstanding this leads to underestimating the algorithm's efficiency and elegance.

Quick: Can Kadane's Algorithm find the maximum subarray if the array contains zeros? Commit yes or no.

Common Belief: Zeros in the array break Kadane's Algorithm or cause incorrect results.

Reality: Zeros do not affect Kadane's Algorithm; it handles zeros naturally as part of the sum.

Why it matters: Misbelief about zeros may cause unnecessary code changes or confusion.

Expert Zone

1

Kadane's Algorithm can be adapted to find maximum product subarrays with careful handling of negative numbers and zeros.

2

The algorithm's reset step is a form of pruning that discards suboptimal partial solutions, a key dynamic programming optimization.

3

In streaming data, Kadane's Algorithm can be run incrementally to maintain maximum subarray sums in real time.

When NOT to use

Kadane's Algorithm is not suitable when you need to find maximum subarrays with additional constraints like fixed length, or when the problem involves multidimensional arrays where more complex algorithms are needed.

Production Patterns

Kadane's Algorithm is widely used in financial analysis to find best profit intervals, in signal processing to detect strongest signals, and in competitive programming as a fundamental technique for subarray problems.

Connections

Dynamic Programming

Kadane's Algorithm is a simple form of dynamic programming that builds solutions from previous results.

Understanding Kadane's Algorithm helps grasp the core idea of dynamic programming: solving complex problems by combining solutions to smaller subproblems.

Greedy Algorithms

Kadane's Algorithm uses a greedy choice to reset the sum when negative, discarding suboptimal paths.

Recognizing the greedy step in Kadane's Algorithm clarifies how local decisions can lead to a global optimum in some problems.

Financial Trading Analysis

Maximum subarray sums correspond to best buy-sell intervals for profit maximization in stock prices.

Knowing Kadane's Algorithm helps understand how traders identify the most profitable periods efficiently.

Common Pitfalls

#1 Not handling all-negative arrays correctly.

Wrong approach:

int maxSubArray(int* nums, int numsSize) {
int max_so_far = 0;
int current_max = 0;
for (int i = 0; i < numsSize; i++) {
current_max += nums[i];
if (current_max > max_so_far) max_so_far = current_max;
if (current_max < 0) current_max = 0;
}
return max_so_far;
}

Correct approach:

int maxSubArray(int* nums, int numsSize) {
int max_so_far = nums[0];
int current_max = 0;
for (int i = 0; i < numsSize; i++) {
current_max += nums[i];
if (current_max > max_so_far) max_so_far = current_max;
if (current_max < 0) current_max = 0;
}
return max_so_far;
}

Root cause:

Initializing max_so_far to zero causes incorrect results when all numbers are negative.

#2 Trying to store all subarray sums to find maximum.

Wrong approach:

int maxSubArray(int* nums, int numsSize) {
int max_sum = nums[0];
for (int i = 0; i < numsSize; i++) {
for (int j = i; j < numsSize; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += nums[k];
}
if (sum > max_sum) max_sum = sum;
}
}
return max_sum;
}

Correct approach:

Use Kadane's Algorithm with a single loop and constant extra space as shown in previous steps.

Root cause:

Not knowing the efficient linear-time approach leads to inefficient brute force solutions.

#3 Resetting current sum incorrectly inside the loop.

Wrong approach:

for (int i = 0; i < numsSize; i++) {
if (current_max < 0) current_max = 0;
current_max += nums[i];
if (current_max > max_so_far) max_so_far = current_max;
}

Correct approach:

for (int i = 0; i < numsSize; i++) {
current_max += nums[i];
if (current_max > max_so_far) max_so_far = current_max;
if (current_max < 0) current_max = 0;
}

Root cause:

Resetting before adding current element loses the contribution of the current element.

Key Takeaways

Kadane's Algorithm finds the maximum sum of a continuous subarray in linear time by tracking current and maximum sums.

Resetting the current sum when it becomes negative ensures the algorithm focuses on promising subarrays only.

Handling edge cases like all-negative arrays requires initializing the maximum sum carefully.

Kadane's Algorithm is a simple yet powerful example of dynamic programming and greedy strategy combined.

Understanding this algorithm unlocks efficient solutions to many real-world problems involving sequences and intervals.

Practice

1. What does Kadane's Algorithm primarily help to find in an array?

easy

A. The total sum of all elements

B. The minimum element in the array

C. The maximum sum of a contiguous subarray

D. The maximum product of any two elements

Solution

1. Step 1: Understand the problem Kadane's Algorithm solves

   Kadane's Algorithm is designed to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

2. Step 2: Compare with other options

   Options B, C, and D describe different problems unrelated to Kadane's Algorithm.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option C

4. Quick Check:

   Maximum subarray sum = maximum sum of contiguous elements [OK]

Hint: Kadane finds max sum in continuous parts of array [OK]

Common Mistakes:

• Confusing max sum with max product
• Thinking it finds minimum element
• Assuming it sums all elements

2. Which of the following is the correct initialization step in Kadane's Algorithm in C?

easy

A. int max_so_far = INT_MIN, max_ending_here = 0;

B. int max_so_far = 0, max_ending_here = 0;

C. int max_so_far = 0, max_ending_here = INT_MIN;

D. int max_so_far = NULL, max_ending_here = 0;

Solution

1. Step 1: Understand initialization in Kadane's Algorithm

   We initialize max_so_far to the smallest integer (INT_MIN) to handle arrays with all negative numbers correctly, and max_ending_here to 0 to start accumulating sums.

2. Step 2: Evaluate each option

   int max_so_far = 0, max_ending_here = 0; initializes max_so_far to 0, which fails for all negative arrays. int max_so_far = 0, max_ending_here = INT_MIN; incorrectly initializes max_ending_here to INT_MIN. int max_so_far = NULL, max_ending_here = 0; uses NULL which is invalid for int.

3. Final Answer:

   int max_so_far = INT_MIN, max_ending_here = 0; -> Option A

4. Quick Check:

   Use INT_MIN for max_so_far to handle negatives [OK]

Hint: Start max_so_far at INT_MIN to handle negatives [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results
• Using NULL for integer variables
• Swapping initial values of variables

3. What is the output of the following C code using Kadane's Algorithm?

int arr[] = {-2, 3, 2, -1};
int n = 4;
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < n; i++) {
    max_ending_here += arr[i];
    if (max_so_far < max_ending_here) max_so_far = max_ending_here;
    if (max_ending_here < 0) max_ending_here = 0;
}
printf("%d", max_so_far);

medium

A. 4

B. 5

C. 3

D. -1

Solution

1. Step 1: Trace the loop and update sums

   Iteration 0: max_ending_here = 0 + (-2) = -2; max_so_far = max(INT_MIN, -2) = -2; max_ending_here < 0, reset to 0.
   Iteration 1: max_ending_here = 0 + 3 = 3; max_so_far = max(-2, 3) = 3; max_ending_here >= 0, no reset.
   Iteration 2: max_ending_here = 3 + 2 = 5; max_so_far = max(3, 5) = 5; max_ending_here >= 0, no reset.
   Iteration 3: max_ending_here = 5 + (-1) = 4; max_so_far = max(5, 4) = 5; max_ending_here >= 0, no reset.

2. Step 2: Final max_so_far value

   After loop ends, max_so_far is 5, which is the maximum subarray sum.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Max subarray sum = 5 [OK]

Hint: Add elements, reset sum if negative, track max sum [OK]

Common Mistakes:

• Not resetting max_ending_here when negative
• Confusing max_so_far with current sum
• Incorrectly summing non-contiguous elements

4. Identify the bug in this Kadane's Algorithm implementation in C:

int maxSubArraySum(int arr[], int n) {
    int max_so_far = 0, max_ending_here = 0;
    for (int i = 0; i < n; i++) {
        max_ending_here += arr[i];
        if (max_so_far < max_ending_here) max_so_far = max_ending_here;
        if (max_ending_here < 0) max_ending_here = 0;
    }
    return max_so_far;
}

medium

A. max_so_far should be initialized to INT_MIN

B. max_ending_here should be initialized to INT_MIN

C. Loop should start from i = 1

D. Return statement should return max_ending_here

Solution

1. Step 1: Analyze initialization of max_so_far

   Initializing max_so_far to 0 fails when all array elements are negative, as max_so_far will never update to a negative number.

2. Step 2: Correct initialization and effect

   Setting max_so_far to INT_MIN ensures the algorithm correctly finds the maximum subarray sum even if all numbers are negative.

3. Final Answer:

   max_so_far should be initialized to INT_MIN -> Option A

4. Quick Check:

   Use INT_MIN for max_so_far to handle negative arrays [OK]

Hint: Initialize max_so_far to INT_MIN for negative arrays [OK]

Common Mistakes:

• Initializing max_so_far to 0 causes wrong max for negatives
• Changing loop start index unnecessarily
• Returning wrong variable

5. Given an array int arr[] = {-3, -2, -1, -4}, what is the maximum subarray sum using Kadane's Algorithm?

hard

A. -3

B. 0

C. -10

D. -1

Solution

1. Step 1: Understand Kadane's behavior with all negative numbers

   When all numbers are negative, resetting max_ending_here to 0 loses the maximum negative number. Proper Kadane's initialization with max_so_far = INT_MIN helps track the largest negative number.

2. Step 2: Trace the array values

   max_so_far starts at INT_MIN.
   i=0: max_ending_here = -3; max_so_far = -3; reset max_ending_here to 0 since negative.
   i=1: max_ending_here = -2; max_so_far = max(-3, -2) = -2; reset max_ending_here to 0.
   i=2: max_ending_here = -1; max_so_far = max(-2, -1) = -1; reset max_ending_here to 0.
   i=3: max_ending_here = -4; max_so_far = max(-1, -4) = -1; reset max_ending_here to 0.

3. Final Answer:

   -1 -> Option D

4. Quick Check:

   Max negative number = -1 [OK]

Hint: Max subarray in negatives is max single element [OK]

Common Mistakes:

• Returning 0 instead of max negative
• Not handling all negative arrays
• Assuming sum must be positive