# Maximum Subarray Problem (Kadane’s algorithm)

Given an array of integers, find contiguous subarray within it which has the largest sum.

For example,

Input:  {-2, 1, -3, 4, -1, 2, 1, -5, 4}

Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.

We can easily solve this problem in linear time using kadane’s algorithm. The idea is to maintain maximum (positive sum) sub-array “ending” at each index of the given array. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous index.

## C++

Output:

The sum of contiguous sub-array with the largest sum is 6

## Java

Output:

The sum of contiguous sub-array with the largest sum is 6

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Above code doesn’t handle the case when all elements of the array are negative. If the array contains all negative values, the answer is the maximum element. We can easily place this check before continuing to the algorithm. The implementation can be seen below in C++ and Java –

## C++

Output:

The sum of contiguous sub-array with the largest sum is -2

## Java

Output:

The sum of contiguous subarray with the largest sum is -2

But this approach requires two traversals of the input array. We can easily modify the main algorithm to handle negative integers as well. The C++ and Java implementation is shown below –

## C++

Output:

The sum of contiguous subarray with the largest sum is -2

## Java

Output:

The sum of contiguous sub-array with the largest sum is -2

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming.

Related Post: Print continuous subarray with maximum sum

(2 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

I like this site more than every other coding site. Quality of post is definitely to the point and better. And, last but not the least, you guys have better font size and overall look of the site. Keep it up and thank you! 🙂

Guest
FunniestClown

True that.
I come here whenever I feel confused in g4g 😉

Guest

The fact that every problem here “can be easily solved” makes me feel quite stupid. lol

Guest

Is Kadane Algorithm Divide and Conquer too? Sorry if this is a stupid question. Thanks

Guest

Kadane’s algorithm is a Dynamic programming algorithm, not Divide & Conquer.

Guest

I think 2 & 3 solutions were swapped.

Guest

In first solution, you can check greater first then check negative result. This will work for all negative number array.