Jump to content
  • Advertisement
Sign in to follow this  
roos

Technical question

This topic is 4805 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I was looking through some technical interview questions out of curiosity's sake... This one stumped me for a while:
Quote:
You're given an array containing both positive and negative integers. Find the subarray (contiguous elements) with the largest sum, in O(n) time.
I don't really know if I could solve this on the spot in an interview (maybe with a clue from the interviewer), but I did manage to come up with a solution. Anyways, if anyone else wants to take a shot at this, please post your solution here. I'd be curious to see what other approaches you guys can come up with to this problem. Thanks, roos (my solution below)
void Find( long *values, const long arraySize, long &low, long &high )
{
	int *sums = new int[arraySize];

	int sum = 0;

	// Create an array called "sums", which holds the cumulative sum of values
	// So, sums[6] = values[0] + values[1] + ... + values[6]

	for( long j = 0; j < arraySize; ++j )
	{
		sum += values[j];
		sums[j] = sum;
	}

	// lowValue stores the point which the algorithm considers to be the most
	// likely start of the subarray.

	int lowValue = values[0] - sums[0];

	// bestValue: keeps trakc of the highest sum we have found so far	
	int bestValue = 0xFFFFFFFF;

	
	int lowIndex = 0;         // current index of most likely start of subarray

	int	bestHighIndex = 0,    // current "best" subarray we have found
		bestLowIndex = 0;

	// iterate through values and find largest subarray
	for( long j = 0; j < arraySize; ++j )
	{
		// check for point more likely to be start of subarray
		if( values[j] - sums[j] > lowValue )
		{
			lowIndex = j;
			lowValue = values[j] - sums[j];
		}

		// compare the current point to the start of subarray. If the sum
		// inside this interval is higher than any sum we've found, use it.

		if( sums[j] + lowValue > bestValue )
		{
			bestHighIndex = j;
			bestLowIndex  = lowIndex;
			bestValue = sums[j] + lowValue;
		}
	}

	delete [] sums;

	// return the subarray range

	low = bestLowIndex;
	high = bestHighIndex;
}

Share this post


Link to post
Share on other sites
Advertisement

int greatest_sum(const int* nums, const int count)
{
int total = 0;
int best = 0;

for(int i = 0; i < count; i++)
{
total += nums;
if(total > best)
best = total;

else if(total < 0)
total = 0;
}

return best;
}




[edit] if you want the actual range, assign best_start and best_end when you assign to best, and reset start when you reset total.

Share this post


Link to post
Share on other sites
It also doesn't come close to working properly, because it assumes incorrectly that the greatest-summing subarray does not contain any negative elements. Consider for example the array {10, -1, 10}. The subarray with the greatest total is the whole thing.

Share this post


Link to post
Share on other sites
Hehe :) Actually I had the same reaction when I glanced at that code because it looks so simple, but if you look carefully, it does work. I almost took a similar approach but I got thrown off by stupid things like, what if the max subarray's sum is zero, then this wouldn't work... But, first of all, the question states that the array has both negative and positive members. And secondly, if the max subarray had a negative sum, that means the entire array is negative. In that case, finding the max subarray is a trivial special case, so all you have to do is find the max element (or even just an empty array if that's allowed).

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
It also doesn't come close to working properly, because it assumes incorrectly that the greatest-summing subarray does not contain any negative elements. Consider for example the array {10, -1, 10}. The subarray with the greatest total is the whole thing.

Sure it does. It only resets total is it drops below zero. That -1 results in total equalling 9, which is less than 10 [the current best], so nothing happens. Then total becomes 19, and best becomes the entire array.

*edit: that reset condition is sufficient, because anytime you have a negative sum your total actually goes up by chosing an empty subarray.

CM

Share this post


Link to post
Share on other sites
Off-the-cuff, this problem is np-hard and cannot be done in O(n) time.

Sub-arrays are continuous, but they can start and end anywhere. The only way to find the highest sum is to calculate them all. You have to test all lengths of sub-arrays and all starting & ending positions.

You can start with roos algorithms, which computes the running total, then rip through it n times (have to check for k in [1,n] ) and take the difference between every k'th elements in the sum. That ought to tell you the sum for that range.

Share this post


Link to post
Share on other sites
Quote:
Original post by Shannon Barber
Off-the-cuff, this problem is np-hard and cannot be done in O(n) time.

Sub-arrays are continuous, but they can start and end anywhere. The only way to find the highest sum is to calculate them all. You have to test all lengths of sub-arrays and all starting & ending positions.

You can start with roos algorithms, which computes the running total, then rip through it n times (have to check for k in [1,n] ) and take the difference between every k'th elements in the sum. That ought to tell you the sum for that range.

I'm pretty sure ajas' algorithm is correct, and linear. The subarray can't start anywhere. They have to start at the begining, or after a negative value. It also can't end anywhere. It has to end at the end, or at a positive value that is followed by a negative value. Both of these are pretty easy to prove. If either position is negative, removing that element will increase the total. If the begining is preceded by a positive value, or the end is followed by a positive value, adding the extra element will increase the total. So any bounds except those are guarenteed to be sub-optimal. Any time a running total has a negative value, an empty sub array would actually be a higher sum than the current one, so starting over is the right thing to do. From there, the rest of the algorithm is pretty straight forward.

CM

Share this post


Link to post
Share on other sites
It only works for roos's example case, consider:

e.g.


int main()
{
int numbers[] = {-1,-2,-3,4,-1,-1,2,3,-1};
int n = sizeof(numbers)/sizeof(numbers[0]);

int sum = greatest_sum(numbers, n);
}








Returns 7.

The answer is 5 starting at 6 for a run of 2.


Here's another good test case:
{-10,-10,-10,4,-10,-10,3,-1,3,-10};
The answer is 5 starting at 6 for a run of 3.

Then you have to start trying pathological cases:
{-10,-10,-10,-1,-10,-10};
-1 start at 3 run of 1.

Share this post


Link to post
Share on other sites
Yeah, both our algorithms are correct although ajas's is much more efficient :)

For mine, I basically used the fact that the sum of a subarray is:

sum(i to j) = value(i) + sum(0 to j) - sum(0 to i)

So the code looks for points where value(i) - sum(0 to i) is maximized- those are the "suspected" minimum bounds for the subarray. Then, on every iteration it calculates the sum from suspected min bound to the current point, and saves it in "bestValue" if it's the biggest sum found so far.

Actually, since my code only references sums[j] and never has to look forward or ahead of the current position, I could have just used a single sum variable instead of an array which would have made it way more efficient. (duh)


Quote:
int numbers[] = {-1,-2,-3,4,-1,-1,2,3,-1};
Returns 7
The answer is 5 starting at 6 for a run of 2.


I think the return value of 7 is fine... It can be done with {4, -1, -1, 2, 3}

roos

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!