CareerCup

the result would be: {1,-2,4, -2, 6}? You miss 4. The sum is 7 which is equal to the given MaxSum.

Is it fine that the subarray elements are not continous?

The question reads less or equal to the given MaxSum.If this is the case then we can have both {1,-2,4,5,-2} or {1,-2,4,-2,6} so how do you decide what to choose?

Could anybody retype or word the question a little more clearly.

reduce problem to 0-1 knapsack problem with the value of each item is one.

I believe subarray implies continuous, so for array = {1, -2, 4, 5, -2, 6, 7} and max=7, answer should be {1, -2, 4, 5, -2}

I believe it can be solved even if you don't consider it to be a contiguous block. In such a case you would have to consider dynamic programming. I solved the problem using lisp. Here is the code

(defun maxsum(list maxsum &optional sublist)
  (cond ((= (length list) 1) (if (<= (apply #'+ (append sublist list))
				     maxsum)
				 (reverse (append sublist list))
				 (reverse sublist)))
	(t (let ((list1 (if (<= (apply #'+ (cons (first list) sublist))
				maxsum)
			    (cons (first list) sublist)
			    sublist))
		 (list2 (maxsum (rest list)
				maxsum
				(if (<= (apply #'+ (cons (first list) sublist))
					maxsum)
				    (cons (first list) sublist)
				    sublist))))
						    
	     (if (> (length list1)
		    (length list2))
		 list1
		 list2)))))

The output is as follows

maxsum = 7
(maxsum '(1 -2 4 5 -2 6 7) 7)
(6 -2 4 -2 1)

Maxsum = 10;
(maxsum '(1 -2 4 5 -2 6 7) 10)
(1 -2 4 5 -2)

someone is trying to get homework done again...

Sorry for the confusing, if there are more results, you will only return one result set, the sub array elements are not necessary continually.
Anonymous, can you come up a c code? thanks

Its better to sort the array in assending order, then add each element one-by-one till sum <= maxsum

Complexity N(log N)

@Anonymous on October 05, 2009
Would you like to post your solution is some other language, say C/C++/Java etc or at least put the pseudo-code so that it'll be a bit easier for all of us to follow your solution. Thank you.

Assumptions:

- subarray MUST be continuous, else we'd just return all positive integers, or if the largest int should they all be <= 0.

- The FIRST subarray is returned should there be multiple subarrays with the same max sum

- Should the resulting max subarray end in a zero, it will not be picked up. For instance: { 1, 0, 1, 0 } will return { 1, 0 , 1 }. This goes for { 1, 0, 1, 0, 0, 0 ...} as well.

Pseudo Code:

- You will need at least 6 counters to keep track of values.  These will all be initialized as zero at the start, except for max value being set to the smallest possible integer (Integer.MIN_VALUE in Java).
   - Max Sum
   - Current Sum
   - Start Index
   - End Index
   - Cursor
   - Max Value

for( 0 to array length ) {
     add current value (array[i]) to your current sum counter.

   if( current sum > max sum ) {  // Continue your max subarray since it is larger than previous
        max sum is now = current sum
        set start position of your subarray to cursor
        set end position of your subarray to current position
   }
   if ( current sum < 0 ) { // Break your max subarray because it is less than 0
        set current sum back to 0
        update cursor to current position + 1
   }
   if ( current value > max value ) { // Keep track of max value if all values are <= 0
        set max value to current value
   }
}

if( end != 0 ) { // You know a max subarray containing at least 1 positive integer exists
   print max sub array
}
else { // Array was filled with integers <= 0
   print max value
}

The runtime order of this algorithm is O(n) as it only uses a for loop to traverse from beginning to end.

If the question is abt contiguous subarray , then here is the soln :
for(i=0;i<n;i++)
{
curr = curr + a[i];
if( curr > max )
{
max = curr;
}
else if(curr < 0)
{
curr = 0;
}
}

agrees with nobody ! :)

Here would be the recursive solution:

Opt(j, w)=Max(a[j]+Opt(j-1, MAXSUM-a[j]), Opt(j-1, MAXSUM));

more over you are maximizing the sum! shouldnt you be maximizing the number of elements considered in contributing to the SUM ? (i.e. Max(1 + Opt(j-1,..), Opt(..)) instead of Max(a[j]+...)) Correct me if am wrong.

how about multiply each element by -1 and then solve it as maximum sum problem?

If we fix the beginning of the sub array to be x then finding the longest sub-array would be straightforward (by moving the ending of the sub-array y one position at a time until the sum is larger than maxSum). Now let's consider what happens when we move x one position to the left: the ending point of the longest sub-array staring at x+1 will either be less than y (in which case this sub-array can be ruled out from being a candidate for the longest because it is shorter than the previous one) or greater than y. If the new ending point is greater than the current y we can find the new ending point by moving the current ending point one at a time until the sum exceeds maxSum. If we continue this process and keep track of the length, beginning and end, of the longest sub array seen so far then after whole array is scanned we arrive at the longest sub-array.

Pseudo code:

for (int x = 0; x < n; x++)
{
sum = sum - a[x];
while (sum < maxSum)
{
sum += a[y];
y++;
}
if (currentMaxLen < y - x)
{
currentMaxLen = y - x;
currentMaxBegining = x;
currentMaxEnding = y;
}
}