   Challenging programming question
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  
  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;<br>    }<br>    *dest_size = j;<br>}<br><br><br>  I that''s O(n) time, right? Time would increase linearly based &#111;n the size of the array.  </i>   ;  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.  ;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  );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).  ;    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 heheRaj  ;  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 -- ¦þ______________________________  ;  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];  int maxSoFar = 0int maxEndingHere = 0for i = 1 to N do begin   maxEndingHere = max( 0, maxEndingHere + A[i] )   maxSoFar = max( maxSoFar, maxEndingHere )endreturn(MaxSoFar)   This code should do it.[edited by - Ranok on September 15, 2002 7:19:20 PM];  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, 10becomes-3, 30, -5, 8, -15, 10The 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, 10Your 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, 10Remove 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.  