Largest Sum Contiguous Subarray | Kadane Algorithm

Given an array array of N integers. Find the contiguous sub-array with maximum sum.

Let’s look at the very first solution which comes to our mind.

Along with the post, you can refer to my video on youtube which explains the solution in depth :
Link to Youtube : https://youtu.be/xWEK1yQZudo

We should always first find the naive solution to any DS question and then try to optimise it, because it’s always better to solve it using brute force algorithm than not able to solve it all.
And once you have found the solution using brute force, you automatically start getting ideas to improve it because confidence is all you require in the interview.

So the naive solution would be having two loops and finding sum of every possible subarray and compare it will maximum sum till now and update the maximum sum when you find a larger value.
Please note every element itself is a subarray so you need to take care of that in the code.
So the code for this solution will look like following :

public static int findMaxSumSubArray(int arr[]) {


	int maxSum = arr[0];

	int currentSum = arr[0];

	for (int i = 0; i < arr.length ; i++) {

		maxSum = Math.max(maxSum, arr[i]);

		currentSum = arr[i];

		for (int j = i + 1; j < arr.length; j++) {

			currentSum += arr[j];

			maxSum = Math.max(maxSum, currentSum);

		}
	}
	return maxSum;
}

Time Complexity : O(n²)
Space Complexity : O(1)

Can we have a better solution?
You should always ask this question to yourself whenever you find a solution.
So better solution would be one which can find the solution in a single loop which would make it linear complexity.

If I ask you what is the maximum sum subarray ending at a particular index?
Take your time to think, i really want you to find the answer yourself. Because you will be much more happy if you spend 5 minutes and find the solution yourself then just straight forward jumping to the solution.

So maximum sum subarray ending at a particular index would be either the element itself, or sum of element + maximum sum subarray ending at the previous index.

Confused?
Read it again.
Still confused?

Go to my video for more in depth explanation. https://youtu.be/xWEK1yQZudo

So code would look like:

public static int findMaxSumSubArray(int arr[]) {

	int globalMax = arr[0];

	int maxEndingHere = arr[0];

	for (int i = 1; i < arr.length; i++) {

		maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);

		globalMax = Math.max(globalMax, maxEndingHere);

	}

	return globalMax;
}

Time Complexity : O(n)
Space Complexity : O(1)

The solution is so simple, and if you follow how i explained you, you will never really find this question difficult again.

I understand you might be thinking the solution is so simple, then why at most places you find multiple solutions which are hard to understand and they are not designed to run for every possible test case.
The solution i have explained above works well for all possible inputs (try running the solution with input array which contains all negative numbers.

Home work
As always, i have a homework for you, i want you to try an extended version of this question, along with the maximum sum you now need to print the subarray as well.
Do try this, and if you are stuck somewhere post in comments, i will be happy to help.

Keep Learning.

1 thought on “Largest Sum Contiguous Subarray | Kadane Algorithm

Leave a Reply

Your email address will not be published.