Kadane’s Algorithm: Maximum Subarray Sum

Problem: Given an array Arr[] of N integers. Find the contiguous sub-array(containing at least one number) which has the maximum sum and return its sum.

Example:

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

Explore Free Engineering Handwritten Notes!
Download Now
We earn a commission if you make a purchase, at no additional cost to you.

Input: [-3, -4, 5, -1, 2, -4, 6, -1]
Output: 8
Explanation: Subarray [5, -1, 2, -4, 6] is the max sum contiguous subarray with sum 8.

Input: [-2, 3, -1, 2]
Output: 4
Explanation: Subarray [3, -1, 2] is the max sum contiguous subarray with sum 4.

We would be solving the problem by following approaches –

  • Simple approach
  • Efficient Approach: Kadane’s Algorithm

Solution in C++

#include <iostream>
#include <climits>
using namespace std;

int maxSubarraySum(int arr[], int n) {
    int max_sum = INT_MIN;  // Initialize max_sum as negative infinity
    int current_sum = 0;

    for (int i = 0; i < n; i++) {
        current_sum += arr[i];

        // If current_sum becomes negative, reset it to 0
        if (current_sum < 0) {
            current_sum = 0;
        }

        // Update max_sum if current_sum is greater
        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
    }

    return max_sum;
}

int main() {
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    int arr[n];
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int maxSum = maxSubarraySum(arr, n);
    cout << "Maximum subarray sum: " << maxSum << endl;

    return 0;
}

In this C++ code, we define the maxSubarraySum function that takes an array arr and its size n as input and returns the maximum subarray sum. We use the same Kadane’s algorithm logic as explained earlier.

In the main function, we prompt the user to enter the size of the array and its elements. We then call the maxSubarraySum function to get the maximum sum and display it as output.

Note that this implementation requires the <climits> library for the INT_MIN constant.

Solution in Python

def maxSubarraySum(arr, n):
    max_sum = float('-inf')  # Initialize max_sum as negative infinity
    current_sum = 0

    for i in range(n):
        current_sum += arr[i]

        # If current_sum becomes negative, reset it to 0
        if current_sum < 0:
            current_sum = 0

        # Update max_sum if current_sum is greater
        if current_sum > max_sum:
            max_sum = current_sum

    return max_sum

In this algorithm, max_sum represents the maximum sum encountered so far, and current_sum keeps track of the sum of the current subarray. We initialize max_sum as negative infinity to handle cases where all elements in the array are negative.

We iterate through the array and update current_sum by adding the current element. If current_sum becomes negative, we reset it to 0 because including it in the subarray will only decrease the sum. If current_sum is greater than max_sum, we update max_sum with the new maximum value.

Finally, we return max_sum as the result.

The time complexity of this algorithm is O(N) since we iterate through the array once. The auxiliary space complexity is O(1) because we only use a constant amount of additional space to store the maximum and current sums.

Tags: ,

Leave a Reply