Problem Statement

The Maximum Subarray Sum problem involves finding the contiguous subarray (subarray with consecutive elements) within an array of integers that has the largest sum. This is a common problem in computer science and has various applications, including in data analysis and algorithms.

Simple Approach

  • Before diving into Kadane’s Algorithm, let’s briefly discuss a simple approach to solving the Maximum Subarray Sum 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

#include <stdio.h>

const int INT_MIN = -1e9;

int maximumSubarraySum(int arr[], int n) {

int maxSum = INT_MIN;

int i=0;

for(; i <= n - 1; i++) {

int currSum = 0;

int j=i;

for (; j <= n - 1; j++) {

currSum += arr[j];

if (currSum > maxSum) {

maxSum = currSum;

}

}

}

return maxSum;

}

int main() {

// Your code goes here

int a[] = {1, 3, 8, -2, 6, -8, 5};

printf("%d", maximumSubarraySum(a, 7));

return 0;

}

C++ implementation

#include <algorithm>

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

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;

}

int main() {

// Your code goes here;

vector<int> a = {1, 3, 8, -2, 6, -8, 5};

cout << maximumSubarraySum(a) << endl;

return 0;

}

Java implementation

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static 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;

}

public static void main(String args[]) {

// Your code goes here

int a[] = {1, 3, 8, -2, 6, -8, 5};

System.out.println(maximumSubarraySum(a));

}

}

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

if __name__ == "__main__":

# Your code goes here

a = [1, 3, 8, -2, 6, -8, 5];

print(maximumSubarraySum(a));

Efficient Approach – Kadane’s Algorithm

  • Kadane’s Algorithm is an efficient and widely-used approach to solving the Maximum Subarray Sum problem. It works by maintaining two variables: currentSum and maxSum.
  • Kadane’s Algorithm iterates through the array only once, making it more efficient than the simple approach. It updates currentSum with the maximum of the current element or the current element plus the previous currentSum. The maxSum is updated with the maximum of currentSum and the previous maxSum. This way, it keeps track of the maximum subarray sum found so far.
  • The algorithm is easy to implement and is widely used in practice due to its efficiency and simplicity.
  • Implementations in Other Programming Languages
  • You can implement Kadane’s Algorithm in C++, Java, and Python similarly to the C implementation shown above. The key idea remains the same: maintain currentSum and maxSum as you iterate through the array, updating them as needed to find the maximum subarray sum.

C implementation of Efficient approach

#include <stdio.h>

const int INT_MIN = -1e9;

int maximumSubarraySum(int arr[], int n) {

int maxSum = INT_MIN;

int currSum = 0;

int i = 0;

for (; i <= n - 1; i++) {

currSum += arr[i];




if (currSum > maxSum) {

maxSum = currSum;

}

if (currSum < 0) {

currSum = 0;

}

}

return maxSum;

}

int main() {

// Your code goes here

int a[] = {1, 3, 8, -2, 6, -8, 5};

printf("%d", maximumSubarraySum(a, 7));

return 0;

}

C++ implementation of Efficient approach

#include <algorithm>

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

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;

}

int main() {

// Your code goes here;

vector<int> a = {1, 3, 8, -2, 6, -8, 5};

cout << maximumSubarraySum(a) << endl;

return 0;

}

Java implementation of Efficient approach

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static 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;

}

public static void main(String args[]) {

// Your code goes here

int a[] = {1, 3, 8, -2, 6, -8, 5};

System.out.println(maximumSubarraySum(a));

}

}

Python implementation of Efficient approach

def maximumSubarraySum(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

if __name__ == "__main__":

# Your code goes here

print(maximumSubarraySum([1, 3, 8, -2, 6, -8, 5]));

FAQs

1.What is Kadane’s Algorithm, and what problem does it solve?

Kadane’s Algorithm is a technique for finding the maximum sum of a contiguous subarray within an array of numbers. It is commonly used to solve the Maximum Subarray Sum problem.

2.How does Kadane’s Algorithm work?

Kadane’s Algorithm maintains two variables, currentSum and maxSum, while iterating through the array. It continuously updates these variables to find the maximum subarray sum efficiently.

3.Can you explain the basic idea behind Kadane’s Algorithm?

The key idea is to keep track of the maximum sum of subarrays ending at each position in the array. As you iterate through the array, you update the currentSum with the maximum of the current element or the current element plus the previous currentSum. Simultaneously, you update the maxSum with the maximum of currentSum and the previous maxSum.

4.What is the time complexity of Kadane’s Algorithm?

Kadane’s Algorithm has a time complexity of O(n), where n is the number of elements in the input array. It is highly efficient and suitable for large datasets.

5.Is Kadane’s Algorithm suitable for both positive and negative numbers in the array?

Yes, Kadane’s Algorithm works for arrays containing both positive and negative numbers. It handles cases where the maximum subarray sum includes negative numbers.

Categorized in:

Problems

Tagged in:

, , , , , , , , , , , , ,