# 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

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon