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

Overview - Kadane's Algorithm Maximum Subarray

What is it?

Kadane's Algorithm is a simple and efficient way to find the maximum sum of a continuous part (subarray) of a list of numbers. It looks at each number and decides whether to add it to the current sum or start fresh from that number. This helps find the biggest total you can get from any slice of the list. It works in just one pass through the list, making it very fast.

Why it matters

Without Kadane's Algorithm, finding the maximum subarray sum would take much longer, especially for big lists, because you'd have to check every possible slice. This would be slow and inefficient. Kadane's Algorithm solves this by quickly finding the answer in a single sweep, saving time and computing power. This is important in real-world problems like stock trading, where you want to find the best time to buy and sell for maximum profit.

Where it fits

Before learning Kadane's Algorithm, you should understand arrays (lists of numbers) and the idea of subarrays (continuous parts of arrays). After this, you can explore related topics like divide and conquer methods for maximum subarray, dynamic programming, and problems involving sums and intervals.

Mental Model

Core Idea

At each step, decide whether to keep adding to the current sum or start fresh from the current number to find the maximum subarray sum.

Think of it like...

Imagine walking along a path collecting coins. If the coins you find make your total go down, you might decide to drop your current collection and start counting coins from where you are now, hoping to find a better collection ahead.

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

Step:   Start with first number
Current sum: max(-2, 0 + -2) = -2
Max sum: -2

Next number 1:
Current sum: max(1, -2 + 1) = 1
Max sum: max(-2, 1) = 1

Next number -3:
Current sum: max(-3, 1 + -3) = -2
Max sum: max(1, -2) = 1

... and so on, updating current sum and max sum at each step.

Build-Up - 7 Steps

1

Foundation

Understanding Subarrays and Sums

Concept: Learn what a subarray is and how to calculate its sum.

A subarray is a continuous part of an array. For example, in [1, 2, 3, 4], [2, 3] is a subarray. To find the sum of a subarray, add all its elements. For [2, 3], sum is 2 + 3 = 5. The maximum subarray sum is the largest sum among all possible subarrays.

Result

You can identify subarrays and calculate their sums correctly.

Understanding subarrays and their sums is the foundation for solving the maximum subarray problem.

2

Foundation

Brute Force Approach to Maximum Subarray

Concept: Try all possible subarrays and find the one with the largest sum.

Check every subarray by starting at each index and ending at every index after it. Calculate the sum for each and keep track of the largest sum found. For example, for [1, -2, 3], subarrays are [1], [1, -2], [1, -2, 3], [-2], [-2, 3], [3]. Calculate sums and find the max.

Result

You get the maximum subarray sum but with slow performance for large arrays.

Brute force works but is inefficient; it helps understand the problem but is not practical for big data.

3

Intermediate

Introducing Kadane's Algorithm Logic

🤔Before reading on: do you think adding a negative number always lowers the current sum or can it sometimes help? Commit to your answer.

Concept: At each number, decide whether to add it to the current sum or start fresh from that number.

Keep two variables: current_sum and max_sum. For each number, update current_sum as the maximum of the number itself or current_sum plus the number. Then update max_sum if current_sum is bigger. This way, you skip bad parts and keep track of the best sum so far.

Result

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

Knowing when to reset the current sum prevents carrying negative totals that reduce the maximum sum.

4

Intermediate

Implementing Kadane's Algorithm in C++

🤔Before reading on: do you think Kadane's Algorithm needs extra space proportional to input size or just a few variables? Commit to your answer.

Concept: Write code that uses two variables to track sums and loops through the array once.

int maxSubArray(vector& nums) { int current_sum = nums[0]; int max_sum = nums[0]; for (int i = 1; i < nums.size(); i++) { current_sum = max(nums[i], current_sum + nums[i]); max_sum = max(max_sum, current_sum); } return max_sum; } // Example: nums = [-2,1,-3,4,-1,2,1,-5,4] // Output: 6 (from subarray [4,-1,2,1])

Result

The function returns the maximum subarray sum efficiently.

Using just two variables and one loop makes the algorithm fast and memory efficient.

5

Intermediate

Tracking the Maximum Subarray Indices

🤔Before reading on: do you think Kadane's Algorithm can be modified to find the start and end positions of the max subarray? Commit to your answer.

Concept: Extend the algorithm to remember where the max subarray begins and ends.

Add variables to track the start index of the current sum and update start and end indices when max_sum changes. Example code snippet: int maxSubArray(vector& nums) { int current_sum = nums[0], max_sum = nums[0]; int start = 0, end = 0, temp_start = 0; for (int i = 1; i < nums.size(); i++) { if (nums[i] > current_sum + nums[i]) { current_sum = nums[i]; temp_start = i; } else { current_sum += nums[i]; } if (current_sum > max_sum) { max_sum = current_sum; start = temp_start; end = i; } } // max_sum is the sum, start and end are indices return max_sum; }

Result

You can find both the maximum sum and the exact subarray that produces it.

Tracking indices helps solve real problems where you need to know the subarray, not just the sum.

6

Advanced

Handling All Negative Numbers Case

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

Concept: Kadane's Algorithm still works if all numbers are negative, but you must initialize properly.

If all numbers are negative, the maximum subarray is the single largest number. Initializing current_sum and max_sum to the first element ensures the algorithm picks the largest negative number instead of zero or wrong sums.

Result

The algorithm correctly returns the largest negative number as the max subarray sum.

Proper initialization is crucial to handle edge cases like all negative inputs.

7

Expert

Kadane's Algorithm and Dynamic Programming

🤔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 step, current_sum represents the best subarray sum ending at that position. This uses the principle of optimality: the best solution at position i depends on the best solution at i-1. This is dynamic programming because it breaks the problem into smaller overlapping subproblems and solves them efficiently.

Result

You understand Kadane's Algorithm as a dynamic programming technique with O(n) time and O(1) space.

Recognizing Kadane's Algorithm as dynamic programming connects it to a broad class of efficient problem-solving methods.

Under the Hood

Kadane's Algorithm works by iterating through the array once, maintaining two variables: current_sum and max_sum. current_sum stores the maximum sum of a subarray ending at the current index. At each step, it decides whether to add the current element to current_sum or start fresh from the current element if adding reduces the sum. max_sum keeps track of the highest current_sum seen so far. This approach avoids checking all subarrays by using the fact that the maximum subarray ending at position i can be built from the maximum subarray ending at i-1.

Why designed this way?

Before Kadane's Algorithm, the maximum subarray problem was solved using brute force or divide and conquer methods, which were slower. Kadane's Algorithm was designed to solve the problem in linear time with constant space by leveraging the idea of dynamic programming and optimal substructure. It was a breakthrough because it simplified the problem to a single pass, making it practical for large datasets.

Input Array:  [a1, a2, a3, ..., an]

Iteration:
  ┌─────────────┐
  │ Start i=1   │
  └─────┬───────┘
        │
        ▼
  ┌─────────────┐
  │ current_sum = max(a_i, current_sum + a_i) │
  └─────┬───────┘
        │
        ▼
  ┌─────────────┐
  │ max_sum = max(max_sum, current_sum) │
  └─────┬───────┘
        │
        ▼
  ┌─────────────┐
  │ i = i + 1   │
  └─────┬───────┘
        │
        ▼
  Repeat until i > n

Output: max_sum

Myth Busters - 3 Common Misconceptions

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

Common Belief: Kadane's Algorithm only works if there is at least one positive number in the array.

Reality: Kadane's Algorithm works correctly even if all numbers are negative, as long as it is initialized properly with the first element.

Why it matters: If misunderstood, one might wrongly reject Kadane's Algorithm for negative-only arrays and use slower methods.

Quick: Does Kadane's Algorithm find the maximum subarray sum by checking all possible subarrays? Commit to yes or no.

Common Belief: Kadane's Algorithm checks every possible subarray to find the maximum sum.

Reality: Kadane's Algorithm does not check all subarrays; it uses a clever running sum and resets to avoid unnecessary checks.

Why it matters: Believing it checks all subarrays hides the efficiency and elegance of the algorithm.

Quick: Can Kadane's Algorithm be used to find the maximum product subarray? Commit to yes or no.

Common Belief: Kadane's Algorithm can be directly used to find the maximum product subarray by just replacing sums with products.

Reality: Kadane's Algorithm for sums cannot be directly applied to products because negative numbers and zeros complicate the product calculation; a modified approach is needed.

Why it matters: Misapplying Kadane's Algorithm to product problems leads to incorrect results.

Expert Zone

1

Kadane's Algorithm can be extended to track the start and end indices of the maximum subarray with minimal overhead.

2

The algorithm's logic relies on the principle of optimal substructure, a key dynamic programming concept, which is often overlooked.

3

In some variations, Kadane's Algorithm can be adapted to multidimensional arrays, but this requires more complex handling.

When NOT to use

Kadane's Algorithm is not suitable when you need to find maximum subarrays with additional constraints, like fixed length or non-contiguous elements. For maximum product subarray problems, specialized algorithms are needed. Also, if you want all maximum subarrays (not just one), Kadane's Algorithm alone is insufficient.

Production Patterns

Kadane's Algorithm is widely used in financial software to find the best time intervals for profit, in signal processing to detect strong signals, and in competitive programming as a classic example of dynamic programming. It is often a building block in more complex algorithms involving interval sums.

Connections

Dynamic Programming

Kadane's Algorithm is a simple form of dynamic programming that solves a problem by building on solutions to smaller subproblems.

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

Sliding Window Technique

Both Kadane's Algorithm and sliding window techniques process arrays in linear time by maintaining a running value over a window or segment.

Recognizing the similarity helps in choosing the right approach for problems involving continuous segments.

Financial Trading Strategies

Kadane's Algorithm models the problem of finding the best time to buy and sell stocks for maximum profit, which is a core financial analysis task.

Knowing this connection shows how abstract algorithms solve real-world money problems efficiently.

Common Pitfalls

#1 Initializing current_sum and max_sum to zero instead of the first element.

Wrong approach:

int current_sum = 0;
int max_sum = 0;
for (int i = 0; i < nums.size(); i++) {
current_sum = max(nums[i], current_sum + nums[i]);
max_sum = max(max_sum, current_sum);
}
return max_sum;

Correct approach:

int current_sum = nums[0];
int max_sum = nums[0];
for (int i = 1; i < nums.size(); i++) {
current_sum = max(nums[i], current_sum + nums[i]);
max_sum = max(max_sum, current_sum);
}
return max_sum;

Root cause:

Starting sums at zero causes incorrect results when all numbers are negative because zero is greater than any negative number.

#2 Trying to find maximum subarray sum by sorting the array first.

Wrong approach:

sort(nums.begin(), nums.end());
return accumulate(nums.begin(), nums.end(), 0);

Correct approach:

Use Kadane's Algorithm to find the maximum sum of a continuous subarray without sorting.

Root cause:

Sorting breaks the original order, losing the continuous subarray property.

#3 Assuming Kadane's Algorithm works for maximum product subarray without changes.

Wrong approach:

int maxProduct(vector& nums) {
int current_product = nums[0];
int max_product = nums[0];
for (int i = 1; i < nums.size(); i++) {
current_product = max(nums[i], current_product * nums[i]);
max_product = max(max_product, current_product);
}
return max_product;
}

Correct approach:

Use a modified algorithm that tracks both maximum and minimum products at each step to handle negatives and zeros.

Root cause:

Product problems require tracking minimum values too because multiplying two negatives makes a positive.

Key Takeaways

Kadane's Algorithm finds the maximum sum of a continuous subarray in linear time by deciding at each step whether to add the current number or start fresh.

It uses only two variables, making it very efficient in both time and space.

Proper initialization is crucial, especially when all numbers are negative, to avoid incorrect results.

The algorithm is a simple but powerful example of dynamic programming and optimal substructure.

Understanding Kadane's Algorithm helps solve real-world problems like stock trading and signal processing efficiently.

Practice

1. What does Kadane's Algorithm primarily find in an array of integers?

easy

A. The total sum of all elements

B. The minimum element in the array

C. The maximum product of any two elements

D. The maximum sum of a contiguous subarray

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 options with the algorithm's purpose

   Options A, B, and D do not describe the main goal of Kadane's Algorithm. Only The maximum sum of a contiguous subarray correctly states it finds the maximum sum of a contiguous subarray.

3. Final Answer:

   The maximum sum of a contiguous subarray -> Option D

4. Quick Check:

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

Hint: Kadane finds max sum in a continuous slice [OK]

Common Mistakes:

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

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

easy

A. int max_so_far = INT_MIN, max_ending_here = 0;

B. int max_so_far = INT_MAX, max_ending_here = INT_MAX;

C. int max_so_far = 0, max_ending_here = INT_MIN;

D. int max_so_far = 0, max_ending_here = 0;

Solution

1. Step 1: Understand variable roles in Kadane's Algorithm

   max_so_far stores the maximum sum found so far, so it should start very low (INT_MIN) to allow any sum to replace it. max_ending_here tracks the current subarray sum and starts at 0.

2. Step 2: Check each option's initialization

   int max_so_far = INT_MIN, max_ending_here = 0; correctly initializes max_so_far to INT_MIN and max_ending_here to 0. Other options either start max_so_far at 0 or INT_MAX, which can cause incorrect results.

3. Final Answer:

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

4. Quick Check:

   max_so_far = INT_MIN, max_ending_here = 0 [OK]

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

Common Mistakes:

• Initializing max_so_far to 0 causes wrong results with negatives
• Setting max_ending_here to INT_MIN breaks logic
• Using INT_MAX causes overflow issues

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

int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = 9;
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;
}
std::cout << max_so_far << std::endl;

medium

A. 6

B. 7

C. 5

D. 4

Solution

1. Step 1: Trace Kadane's Algorithm on the array

   Iterate through arr: max_ending_here and max_so_far update as follows:
   - i=0: max_ending_here=-2, max_so_far=-2, reset max_ending_here=0
   - i=1: max_ending_here=1, max_so_far=1
   - i=2: max_ending_here=-2, max_so_far=1, reset max_ending_here=0
   - i=3: max_ending_here=4, max_so_far=4
   - i=4: max_ending_here=3, max_so_far=4
   - i=5: max_ending_here=5, max_so_far=5
   - i=6: max_ending_here=6, max_so_far=6
   - i=7: max_ending_here=1, max_so_far=6
   - i=8: max_ending_here=5, max_so_far=6

2. Step 2: Identify maximum subarray sum

   The maximum sum found is 6, which corresponds to subarray [4, -1, 2, 1].

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Max subarray sum = 6 [OK]

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

Common Mistakes:

• Not resetting max_ending_here when negative
• Confusing max_so_far with current sum
• Miscounting subarray sums

4. Identify the bug in this Kadane's Algorithm implementation and select the fix:

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. Remove resetting max_ending_here to 0

B. Initialize max_ending_here to INT_MIN instead of 0

C. Initialize max_so_far to INT_MIN instead of 0

D. Change loop to start from i = 1

Solution

1. Step 1: Analyze initialization impact on negative arrays

   Starting max_so_far at 0 causes incorrect results if all array elements are negative, as max_so_far will never update to a negative sum.

2. Step 2: Fix initialization to handle all negative values

   Setting max_so_far to INT_MIN allows it to update correctly even if all elements are negative, ensuring the maximum subarray sum is found.

3. Final Answer:

   Initialize max_so_far to INT_MIN instead of 0 -> Option C

4. Quick Check:

   max_so_far = INT_MIN fixes negative-only arrays [OK]

Hint: Use INT_MIN for max_so_far to handle negatives [OK]

Common Mistakes:

• Leaving max_so_far at 0 causes wrong max for negatives
• Removing reset breaks algorithm logic
• Changing loop start misses first element

5. Given an array with all negative numbers: int arr[] = {-8, -3, -6, -2, -5, -4}; What is the maximum subarray sum using Kadane's Algorithm?

hard

A. 0

B. -2

C. -3

D. -8

Solution

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

   When all numbers are negative, resetting max_ending_here to 0 causes the algorithm to miss the largest (least negative) number. Proper initialization with max_so_far = INT_MIN helps track the max single element.

2. Step 2: Identify the maximum single element

   The largest number in the array is -2, which is the maximum subarray sum since any longer subarray sum will be smaller.

3. Final Answer:

   -2 -> Option B

4. Quick Check:

   Max single negative element = -2 [OK]

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

Common Mistakes:

• Assuming max sum is 0 by resetting sums
• Ignoring single element max in negative arrays
• Confusing minimum with maximum