Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

RajanSky

Challenging programming question

This topic is 5937 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

Hey, Anyone can figure out this problem? "You''re given an array containing both positive and negative integers and required to find the subarray with the largest sum in O(n) time. Write a C routine for that." I am trying to work through some sample interview questions that people ask programmers... Some of these are pretty tough! I was just wondering if anyone else can figure this one out.. Thanks! Raj

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster


Shouldn''t you just have to loop through the array and add all positive elements to the sub-array? The subarray with the largest sum will be the one with no negative elements, yes?


/* Assumes ''dest'' is big enough to store sub-array (it should be as big as ''src'' to be absolutely safe) */
void FindLargestSubArray(
int* src,
int src_size,
int* dest,
int* dest_size)
{
int i, j;
for(i = 0, j = 0; i < src_size; ++i)
{
if(src > 0) dest[j++] = src[i];
}
*dest_size = j;
}


I that''s O(n) time, right? Time would increase linearly based on the size of the array.

Share this post


Link to post
Share on other sites
Oh is that all they''re asking?!?!
I thought by subarray they were meaning that the elements of the array had to be contiguous...

So like, if you had:

2 -25 100 -25 -55, then the largest subarray would be:
2 -25 100, sums up to 77.
I figured you couldn''t just pick out the 2 and the 100 and skip over the -25 which is in between them since that would be really easy then.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
The subarray with the largest sum will be the one with no negative elements, yes?


seems to easy. RajanSky do you mean consecutive subarrays, like 2,3,4 from 1,2,3,4,5 but not 1,3,5?
If so I''m going to have to think about it (ie. I havn''t a clue )

Share this post


Link to post
Share on other sites
quote:
Original post by RajanSky
Oh is that all they''re asking?!?!
I thought by subarray they were meaning that the elements of the array had to be contiguous...

That would be my understanding too.

And I''m guessing they''re wanting something better than the naive solution (test every subset).

Share this post


Link to post
Share on other sites
Yes, I''m almost positive they mean that the elements of the subarray have to be chosen from consecutive elements of the original array.

Also, yeah I''m sure they''re not looking for the naive solution. If you tested every subset, that wouldn''t even be O(n), it would be O(n^2).. So far my approach has been that you have two pointers into the original array defining a "start" and "end" of the subarray in question, and then as you iterate through the array, you keep moving the "end" pointer further out, or moving the "start" pointer forward in the array too, until you somehow "catch" the region of elements in question...
But I have no idea how to do this hehe. I don''t even know if this method would be correct- perhaps you have to make 2 passes through the array or something like that... weird hehe

Raj

Share this post


Link to post
Share on other sites
I would enhance the naive approach with scanning for the next positive integer, and knowing you''ve gone too far when your cumulative total goes below 1 (<=0). That''s a real stumper...then again I''m nowheres near the interview questions.

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Share this post


Link to post
Share on other sites
How about this:
Begin with your 'start and 'end' pointers at the beginning of the array. Look at the first item. If it is positive, keep the end pointer where it is, and incrememt the start pointer. Then, take the item at the start pointer, and add it to the first item (so we keep a running total). If this total is positive, keep the end pointer where it is, and increment the start pointer again. Repeat this procedure. If, at any point, adding the item at the start pointer to the running total would cause the running total to drop below 0, store a copy of the total (the total before adding the new item, that is), and store the start and end pointers. Now, move your end pointer to the current location, and begin incrementing your start pointer again, keeping a new running total.

Did that make any sense?
It should be O(n), because you are only making one pass through the array.

Edit: Oops. This wouldn't actually work.

[edited by - Martee on September 15, 2002 7:27:10 PM]

Share this post


Link to post
Share on other sites

  
int maxSoFar = 0
int maxEndingHere = 0

for i = 1 to N do begin
maxEndingHere = max( 0, maxEndingHere + A[i] )
maxSoFar = max( maxSoFar, maxEndingHere )
end

return(MaxSoFar)


This code should do it.

[edited by - Ranok on September 15, 2002 7:19:20 PM]

Share this post


Link to post
Share on other sites
What''s the "accepted answer?" I don''t know. But maybe we can make our own.

First, consolidate your array. Add up all groups of positive numbers into a single positive entry, and all groups of negative numbers into a single negative entry. So:

-2, -1, 9, 20, 1, -5, 8, -4, -5, -6, 10

becomes

-3, 30, -5, 8, -15, 10

The resulting array will alternate between positive and negative numbers. Now, realize that the first and last elements in the largest subarray will be positive. So you only need to look at the subarray from the first positive to the last positive number. Thus, the "working array" becomes:

30, -5, 8, -15, 10

Your numbers come in pairs of positives and negatives. I''ll put these pairs in parenthases:

(30, -5)(8, -15)(10)

The last number will always exist simply by itself.

Now, find the sums of these pairs. In this case, that''s:
25, -7, 10

Remove any pairs that have negative sums. You''re left with the (consolidated) best subarray. I didn''t keep track of the indeces (of the original array) here, but you could, and you would then have an algorithm for finding the best subarray. It would run in O(n) time.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!