Maximum Subarray Sum: Kadane’s Algorithm

Maximum Subarray Sum

Problem Statement

Subarrays are arrays inside another array which only contains contiguous elements.

Given an array of integers, the task is to find the maximum subarray sum possible of all the non-empty subarrays.

Example:

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

Simple Approach:

The simple approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. Follow the below steps to solve the problem.

  • Run a loop for i from 0 to n – 1, where n is the size of the array.
  • Now, we will run a nested loop for j from i to n – 1 and add the value of the element at index j to a variable currentMax.
  • Lastly, for every subarray, we will check if the currentMax is the maximum sum of all contiguous subarrays.

C implementation

int maximumSubarraySum(int arr[]) {
  int n = sizeof(arr) / sizeof(arr[0]);
  int maxSum = INT_MIN;

  for (int i = 0; i <= n - 1; i++) {
    int currSum = 0;
    for (int j = i; j <= n - 1; j++) {
      currSum += arr[j];
      if (currSum > maxSum) {
        maxSum = currSum;
      }
    }
  }

  return maxSum;

}

C++ implementation

int maximumSubarraySum(vector < int > arr) {
  int n = arr.size();
  int maxSum = INT_MIN;

  for (int i = 0; i <= n - 1; i++) {
    int currSum = 0;
    for (int j = i; j <= n - 1; j++) {
      currSum += arr[j];
      if (currSum > maxSum) {
        maxSum = currSum;
      }
    }
  }

  return maxSum;

}

Java implementation

public int maximumSubarraySum(int[] arr) {
  int n = arr.length;
  int maxSum = Integer.MIN_VALUE;

  for (int i = 0; i <= n - 1; i++) {
    int currSum = 0;
    for (int j = i; j <= n - 1; j++) {
      currSum += arr[j];
      if (currSum > maxSum) {
        maxSum = currSum;
      }
    }
  }

  return maxSum;
}

Python implementation

  def maximumSubarraySum(arr):
       n = len(arr)
       maxSum = -1e8

       for i in range(0, n):
           currSum = 0
           for j in range(i, n):
               currSum = currSum + arr[j]
               if(currSum > maxSum):
                   maxSum = currSum
      
       return maxSum

Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)


Efficient Approach: Kadane’s Algorithm

Kadane’s Algorithm is an iterative dynamic programming algorithm. It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position. Follow the below steps to solve the problem.

  • Define two-variable currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
  • Initialize currSum with 0 and maxSum with INT_MIN.
  • Now, iterate over the array and add the value of the current element to currSum and check
    • If currSum is greater than maxSum, update maxSum equals to currSum.
    • If currSum is less than zero, make currSum equal to zero.
  • Finally, print the value of maxSum.

Dry run of the above approach

C implementation of Efficient approach

int maximumSubarraySum(int arr[]) {
  int n = sizeof(arr) / sizeof(arr[0]);
  int maxSum = INT_MIN;
  int currSum = 0;

  for (int i = 0; i <= n - 1; i++) {
    currSum += arr[i];

    if (currSum > maxSum) {
      maxSum = currSum;
    }

    if (currSum < 0) {
      currSum = 0;
    }
  }

  return maxSum;

}

C++ implementation of Efficient approach

int maximumSubarraySum(vector < int > arr) {
  int n = arr.size();
  int maxSum = INT_MIN;
  int currSum = 0;

  for (int i = 0; i <= n - 1; i++) {
    currSum += arr[i];

    if (currSum > maxSum) {
      maxSum = currSum;
    }

    if (currSum < 0) {
      currSum = 0;
    }
  }

  return maxSum;

}

Java implementation of Efficient approach

public int maximumSubarraySum(int[] arr) {
  int n = arr.length;
  int maxSum = Integer.MIN_VALUE;
  int currSum = 0;

  for (int i = 0; i <= n - 1; i++) {
    currSum += arr[i];

    if (currSum > maxSum) {
      maxSum = currSum;
    }

    if (currSum < 0) {
      currSum = 0;
    }
  }

  return maxSum;
}

Python implementation of Efficient approach

 def maximumSubarraySum(self, arr):
       n = len(arr)
       maxSum = -1e8
       currSum = 0

       for i in range(0, n):
           currSum = currSum + arr[i]
           if(currSum > maxSum):
               maxSum = currSum
           if(currSum < 0):
               currSum = 0
      
       return maxSum

Time complexity: O(N), Where N is the size of the array.
Space complexity: O(1)


Practice Problems –

Flip Problem
Maximum Product Subarray
Maximum Sum Contiguous Subarray


Frequently Asked Questions

Is Kadane’s algorithm Dynamic Programming?

Yes, It is an iterative dynamic programming algorithm.

What should be the maximum subarray sum if all the elements of the array are negative?

It depends if we are considering empty subarray or not. If we consider an empty subarray then the output should be 0 else, the output should be the maximum element of the array(the element closest to 0).

What is the time complexity of Kadane’s algorithm?

The time complexity of Kadane’s algorithm is O(N) where N is the size of the array.

Previous Post

Kotlin Vs Java – Difference Between Java and Kotlin

Next Post

SOAP vs REST – Difference Between REST and SOAP

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡
Take Free Mock Interview
Exit mobile version