Maximum Subarray Sum – Kadane’s Algorithm

Spread the love

Kadane’s technique works by going from left to right throughout the array and calculating the largest sum of all the subarrays that finish at each element. The highest of these values will be the outcome.

The primary problem, however, is how to determine the largest sum of all the subarrays that finish at an element in O(1) time.

We can utilize the maximum sum ending at the previous element to get the maximum sum of the subarray ending at the current element, let’s say maxEnding. Therefore, we have two options for any element:

Option 1: Add the current element to the maximum sum subarray that ends at the previous element in order to extend it. It is usually preferable to expand the subarray if the maximum subarray sum ending at the preceding index is positive.
Option 2: Create a new subarray using the current element as its starting point. It is always preferable to begin a new subarray from the current element if the maximum subarray sum ending at the previous index is negative.

Table of Contents

C++

// C++ Program for Maximum Subarray Sum using Kadane's Algorithm

#include <bits/stdc++.h>
using namespace std;

// Function to find the maximum subarray sum
int maxSubarraySum(vector<int> &arr) {
    int res = arr[0];
    int maxEnding = arr[0];

    for (int i = 1; i < arr.size(); i++) {
      
        // Find the maximum sum ending at index i by either extending 
        // the maximum sum subarray ending at index i - 1 or by
        // starting a new subarray from index i
        maxEnding = max(maxEnding + arr[i], arr[i]);
      
        // Update res if maximum subarray sum ending at index i > res
        res = max(res, maxEnding);
    }
    return res;
}

int main() {
    vector<int> arr = {2, 3, -8, 7, -1, 2, 3};
    cout << maxSubarraySum(arr);
    return 0;
}

C

// C Program for Maximum Subarray Sum using Kadane's Algorithm

#include <stdio.h>
#include <limits.h>

// Function to find the maximum subarray sum
int maxSubarraySum(int arr[], int size) {
    int res = arr[0];
    int maxEnding = arr[0];

    for (int i = 1; i < size; i++) {
        
        // Find the maximum sum ending at index i by either extending 
        // the maximum sum subarray ending at index i - 1 or by
        // starting a new subarray from index i
        maxEnding = (maxEnding + arr[i] > arr[i]) ? 
                                              maxEnding + arr[i] : arr[i];
      
        // Update res if maximum subarray sum ending at index i > res
        res = (res > maxEnding) ? res : maxEnding;
    }
    return res;
}

int main() {
    int arr[] = {2, 3, -8, 7, -1, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("%lld\n", maxSubarraySum(arr, size));
    return 0;
}

Java

// Java Program for Maximum Subarray Sum using Kadane's Algorithm

import java.util.Arrays;

class GfG {

    // Function to find the maximum subarray sum
    static int maxSubarraySum(int[] arr) {
        int res = arr[0];
        int maxEnding = arr[0];

        for (int i = 1; i < arr.length; i++) {
            
            // Find the maximum sum ending at index i by either extending 
            // the maximum sum subarray ending at index i - 1 or by
            // starting a new subarray from index i
            maxEnding = Math.max(maxEnding + arr[i], arr[i]);
          
            // Update res if maximum subarray sum ending at index i > res
            res = Math.max(res, maxEnding);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, -8, 7, -1, 2, 3};
        System.out.println(maxSubarraySum(arr));
    }
}

Python

# Python Program for Maximum Subarray Sum using Kadane's Algorithm

# Function to find the maximum subarray sum
def maxSubarraySum(arr):
    
    res = arr[0]
    maxEnding = arr[0]

    for i in range(1, len(arr)):
        
        # Find the maximum sum ending at index i by either extending 
        # the maximum sum subarray ending at index i - 1 or by
        # starting a new subarray from index i
        maxEnding = max(maxEnding + arr[i], arr[i])
        
        # Update res if maximum subarray sum ending at index i > res
        res = max(res, maxEnding)
    
    return res

arr = [2, 3, -8, 7, -1, 2, 3]
print(maxSubarraySum(arr))

C#

// C# Program for Maximum Subarray Sum using Kadane's Algorithm

using System;

class GfG {
    
    // Function to find the maximum subarray sum
    static int MaxSubarraySum(int[] arr) {
        int res = arr[0];
        int maxEnding = arr[0];

        for (int i = 1; i < arr.Length; i++) {
            
            // Find the maximum sum ending at index i by either extending 
            // the maximum sum subarray ending at index i - 1 or by
            // starting a new subarray from index i
            maxEnding = Math.Max(maxEnding + arr[i], arr[i]);
            
            // Update res if maximum subarray sum ending at index i > res
            res = Math.Max(res, maxEnding);
        }
        return res;
    }

    static void Main() {
        int[] arr = { 2, 3, -8, 7, -1, 2, 3 };
        Console.WriteLine(MaxSubarraySum(arr));
    }
}

JavaScript

// JavaScript Program for Maximum Subarray Sum using Kadane's Algorithm

// Function to find the maximum subarray sum
function maxSubarraySum(arr) {
    let res = arr[0];
    let maxEnding = arr[0];

    for (let i = 1; i < arr.length; i++) {
        
        // Find the maximum sum ending at index i by either extending 
        // the maximum sum subarray ending at index i - 1 or by
        // starting a new subarray from index i
        maxEnding = Math.max(maxEnding + arr[i], arr[i]);
        
        // Update res if maximum subarray sum ending at index i > res
        res = Math.max(res, maxEnding);
    }
    return res;
}

const arr = [2, 3, -8, 7, -1, 2, 3];
console.log(maxSubarraySum(arr));

Output

Time Complexity: O(n), since we are traversing the array only one time.
Auxiliary Space: O(1)