Print Subarray with Maximum Sum using Kadane’s Algorithm - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers (which may include positive numbers, negative numbers, and zeros), your task is to find and print the subarray that has the maximum sum.

If multiple subarrays have the same maximum sum, return the one that appears first. If the array is empty, return an empty result or appropriate message.

Examples❯

Input Array Maximum Sum Subarray Description
[1, 2, 3, -2, 5] 9 [1, 2, 3, -2, 5] The entire array has the maximum sumVisualization
[-1, -2, -3, -4] -1 [-1] All elements are negative; pick the largest single elementVisualization
[4, -1, 2, 1] 6 [4, -1, 2, 1] Maximum sum comes from a mix of positive and negativeVisualization
[-2, -3, 4, -1, -2, 1, 5, -3] 7 [4, -1, -2, 1, 5] Best subarray lies in the middleVisualization
[5] 5 [5] Single-element arrayVisualization
[] 0 [] Empty array has no subarrays, return 0 or empty resultVisualization
[0, 0, 0] 0 [0] All zeros, choose first zero as max sum subarrayVisualization
[2, -1, 2, 3, 4, -5] 10 [2, -1, 2, 3, 4] Subarray before the negative dipVisualization

Solution❯

Understanding the Problem

We are given an array of integers that may include positive numbers, negative numbers, or zeros. Our goal is to find the contiguous subarray that has the highest possible sum. This is commonly known as the "Maximum Subarray" problem.

In simple terms, a subarray is a continuous portion of the original array. We are not allowed to skip elements. We need to return both the maximum sum and the subarray that gives this sum.

Let’s consider an example:

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

We want to find the subarray with the maximum sum. In this case, the correct answer is:

Subarray: [4, -1, 2, 1]  
Maximum Sum: 6

Step-by-Step Approach

To solve this problem, we use a modified version of Kadane's Algorithm. Here's how we will go step-by-step:

  1. Initialize: We start with variables to track the maximum sum so far, the current sum while traversing, and the indices of the start and end of the best subarray.
  2. Traverse: For each element:
    • Add it to the current sum.
    • If the current sum is greater than the maximum so far, update the maximum and store the current subarray boundaries.
    • If the current sum becomes negative, reset it to 0 and mark the next index as a potential start of the next subarray.
  3. Return: At the end of the loop, return the subarray between the best start and end indices, and the maximum sum.

Edge Cases and How We Handle Them

  • All Positive Elements: The sum increases as we include more elements. The whole array is the answer.
  • All Negative Elements: Since adding any two elements will decrease the sum, we pick the single element with the least negative value.
  • Mixed Elements: This is the typical use case. Kadane's algorithm handles it by resetting the sum when needed and updating the subarray bounds.
  • Empty Array: No elements mean no subarray. We return a sum of 0 and an empty subarray.
  • All Zeros: Although all values are the same (0), we still pick a single element. Usually, the first zero is returned with a sum of 0.

Explanation

Imagine you’re walking through the array with a basket. You keep adding numbers to your basket. If the total weight (sum) becomes negative, you drop everything and start a new basket. But every time your basket has the best total so far, you note down the items inside it. By the end, you’ll have the best basket you picked up along the way — the one with the highest total.

Final Result

With the help of this step-by-step strategy and edge case handling, we can always return the correct maximum subarray and its sum, even in tricky cases like all negatives or empty arrays.

Algorithm Steps❯

  1. Given an array arr of integers (positive, negative, or zero).
  2. Initialize max_sum = arr[0], current_sum = arr[0], start = 0, end = 0, and temp_start = 0.
  3. Iterate through the array from index 1:
  4. → If current_sum + arr[i] is less than arr[i], set current_sum = arr[i] and temp_start = i.
  5. → Else, add arr[i] to current_sum.
  6. → If current_sum > max_sum, update max_sum = current_sum, start = temp_start, end = i.
  7. After loop, the subarray from start to end gives the maximum sum.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>

void maxSubarrayWithIndices(int arr[], int n) {
    int maxSum = arr[0], currentSum = arr[0];
    int start = 0, end = 0, tempStart = 0;

    for (int i = 1; i < n; i++) {
        if (arr[i] > currentSum + arr[i]) {
            currentSum = arr[i];
            tempStart = i;
        } else {
            currentSum += arr[i];
        }

        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
    }

    printf("Maximum Sum: %d\n", maxSum);
    printf("Subarray: [");
    for (int i = start; i <= end; i++) {
        printf("%d", arr[i]);
        if (i < end) printf(", ");
    }
    printf("]\n");
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    maxSubarrayWithIndices(arr, n);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Even in the best case, the algorithm must scan the entire array once to track subarray indices and sums.
Average CaseO(n)Each element is visited exactly once while updating the current and maximum subarray sums.
Worst CaseO(n)Regardless of input (positive, negative, mixed), the algorithm always performs a single pass through the array.

Space Complexity❯

O(1)

Explanation: The algorithm uses only a fixed number of variables (like max_sum, current_sum, start, end, temp_start) and no additional data structures, hence constant space.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...