Full Version: Subarray challenge
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Hi, so many time ago. Do the best you can in the next problem...

You have an array of integers, let say a(1),... ,a(n). Find the sub array of a such that the sum a(i) + ... + a(j) is the greatest posible, but if all the integer in the range i..j are negative the sum is 0.

Let me explain this figure out that you have (7, -1, -1, 7). You have the subarray 1..1 the sum is 7; 1..2 sum is 6; 1..3 sum is 5; 1..4 sum is 12.
the sub array 2..2 the sum is 0 (all numbers are negative); 2..3 sum is 0 (all numbers are negative); 2..4 sum is 5. 3..3 sum is 0; 3..4 sum is 6.

:oops: Sorry about my english if you dont understand what i try to say.
Well, here's the brute force approach:
[syntax="qbasic"]DEFINT A-Z

INPUT "Size of set: ", num
IF num < 1 THEN END

DIM array(1 TO num)

' Input each number in the set:
FOR i = 1 TO num
PRINT "#" + LTRIM$(STR$(i)) + ": ";
INPUT "", array(i)

' The only reason you would include a negative number is if it's
' between two positive numbers that make up for it. As in your
' example: (7, -1, -1, 7), it's better to include the -1's so
' that you can have both sevens. Conversely, you'd always want
' to disclude any negatives on the far left or right.
' Example: (-1, -1, 345, -54, 20300), the first two -1's shouldn't
' even be considered.
' This isn't necessary, but it should help speed it up on large
' sets, because the time it takes will increase exponentially as
' the set size increases (because I used brute force, and there's
' probably a faster algorithm).

' Trim negatives off the front:
first = 1
DO UNTIL array(first) > 0

first = first + 1

IF first > num THEN
PRINT "From 1..1, sum: 0"
PRINT "Note: The entire set is zero and/or negative - any subset would"
PRINT " add to zero."


' ...and off the back:
last = num
DO UNTIL array(last) > 0

last = last - 1


' Now we find the best subset using a slow, brute-force attack:
bestI = 0: bestJ = 0: bestSum& = -1
FOR i = first TO last
FOR j = i TO last

' Add up this subset:
sum& = 0
FOR counter = i TO j
sum& = sum& + array(counter)
NEXT counter

' According to the rules, any negative sum is to be consider zero:
IF sum& < 0 THEN sum& = 0

IF sum& > bestSum& THEN
' We have a new champion!
bestI = i
bestJ = j
bestSum& = sum&


' And the winner is...
PRINT "From" + STR$(bestI) + ".." + LTRIM$(STR$(bestJ)) + ", sum:" + STR$(bestSum&)
Good job, but the sum is 0 when all the numbers were negative, not when the sum is negative. when you have (2, -5, 2), in the sub array 1..3 the sum is -1 (not 0). But is easy to modify your program to do this. Again good job, and fast.
So, if all of the numbers in the subset are negative, then the sum is to be zero.

I'm just curious, why? Does this have any real application?

EDIT: Gasp, I can't beleive I said "disclude", that should be exclude. :oops: It was 3 AM in the morning when I wrote that.
Perhaps, just as is stated the problem is theoretical. But i dont imagine that problem, i just get it in my Algorithms II classes.

And thinking, i could associate the array as an priority queue. Each positive value means how urgent is to attend that entry, and negative means that they do not need attention at all.
lol Did you just challenge him to do your homework? :wink:
I think he did, but if he's taking Algorithms II then he should already have known how to do it the brute force way and is probably expected to do something a bit more clever.
This is the typical backtracking with cut of branches problem Tongue
I dont have to do any homework. In class we have a list of problems to practice. They give us an idea of the final examinations.

I just challenges this problem because it seems interesting to me.