Kadane’s Algorithm is a popular and efficient technique for solving the Maximum Subarray Sum problem. Whether you’re working with Java, C++, Python, or C, this algorithm offers a time-saving solution widely used in programming contests and real-world applications.

Problem Statement

The Maximum Subarray Sum problem is all about finding the contiguous subarray (a sequence of consecutive elements) that has the largest sum in a given array of integers. This problem is fundamental in computer science and appears in areas like:

• Stock market analysis

• Climate data patterns

• Signal processing

• Subsequence detection in large datasets

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 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]));

Final Thoughts on Kadanes Algorithm in Java and C++

If you’re dealing with large datasets or real-time applications, Kadane’s Algorithm is a must-have in your problem-solving toolkit. Whether you’re coding in Java, C++, C, or Python, this approach scales efficiently and delivers fast results.

FAQs

1. What does this algorithm solve?

It helps find the subarray within a list of numbers that has the highest possible sum, where the elements in the subarray are consecutive.

2. How does the algorithm work?

It uses two variables: one to track the sum of the current subarray and another to keep track of the highest sum found so far. As it moves through the array, it decides whether to start a new subarray or extend the current one based on which choice gives a higher sum.

3. Can this algorithm handle negative numbers?

Yes, it can. Even if the array contains only negative values, the algorithm still identifies the maximum subarray sum correctly.

4. What is its time complexity?

It runs in linear time, meaning it only needs to go through the array once. This makes it very efficient, especially for large inputs.

5. Where can it be used?

It’s often used in real-world problems such as analyzing trends in data, tracking maximum profits or losses, or processing signals in one-dimensional data.