Today we will be talking about largest sum subarray using O(1) extra space and with O(N) time complexity using Kadane’s algorithm which is based on dynamic programming.

Question: Given an array of size n, find the largest continuous subarray (having at least one element) with the maximum sum.

Now the naive approach to solve this problem is to consider all the possible subarrays and take the max for all those subarray.

Here’s the implementation in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int best = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			int sum = 0;
			for (int k = i; k <= j; k++)
			{
				sum += a[k];
			}
			best = max(best, sum);
		}
	}
	cout << best << endl;
	return 0;
}

Here in the first and second loop we are fixing the starting and ending point of the subarray and in the third loop we are calculating the sum of that subarray and then we take the maximum of our current best answer and the sum we just calculated.

But the problem with this approach is that the time complexity is O(N^3) which is quite high.

We can reduce the time complexity with this approach by storing the prefix sum in an array.

Here’s the implementation in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> sum(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sum[0] = a[0];
	for (int i = 1; i < n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	int best = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			best = max(best, sum[j] - sum[i] + a[i]);
		}
	}
	cout << best << endl;
	return 0;
}

The problem with this approach is that the time complexity is still high O(N^2) and the space complexity is O(N) extra space.

We can still reduce the time and space complexity  to O(N) and O(1) extra space and there are many ways to do it but in this blog we will be doing this using kadane’s algorithm which is based on dynamic programming.

In this algorithm, we maintain two variables named ‘best’ and ‘sum’. In the ‘best’ variable, we store the maximum sum which we have got till the ith index and in the ‘sum’ variable, we store the max sum of the subarray till ith index which do not have a prefix subarray with negative sum.

It seems quite difficult to implement at first but its very easy and can be done in a few lines of code.

Algorithm:

  1. Take two variables named ‘best’ and ‘sum’.
  2. Run a loop from 0 to N-1.
  3. Add the current element to ‘sum’.
  4. If ‘sum’ is greater than ‘best’, make ‘best’ equal to ‘sum’.
  5. If ‘sum’ is less than zero, assign zero to ‘sum’.
  6. Close the loop.

Here’s the implementation in C++

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	int sum = 0;
	int best = INT_MIN;
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		best = max(best, sum);
		sum = max(0, sum);
	}
	cout << best << endl;
	return 0;
}

For each index first we add the ith  element to sum and then we check if it is greater than the current value of ‘best’ and then we check ‘sum’ should not be less than zero.

Now many of you may think , why are we checking if ‘sum’ is greater than zero or not.

The reason is that a prefix array with a negative sum is just a burden for us.

Let’s take an example, it will be all clear

Let’s take the array

-1, 2, -2, 3, 4

In this example , we first go to 1st element and add it to ‘sum’ and as the sum is less than zero(-1) we assign zero to ‘sum’ because if we keep sum = -1 then for the next index we will be already carrying a negative value and it will only lower our answer for the next indices.

That’s all I have and thanks a lot for reading 😉. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance…

Thanks Shiva Gupta for helping us to grow day by day. Shiva is expert in Data Structure and loves to solve competitive problems.


1 Comment

Divyansh Goel · April 5, 2020 at 7:35 pm

Really good explanation. Comparing the optimized solution with the naive solution helped in gaining intuition. Thanks!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert