Subarray challenge

[xhantt]

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.

[Sterling Christensen]

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)
NEXT 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
PRINT "From 1..1, sum: 0"
PRINT
PRINT "Note: The entire set is zero and/or negative - any subset would"
PRINT " add to zero."
PRINT
END
END IF

LOOP

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

last = last - 1

LOOP

' 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&
END IF

NEXT j
NEXT i

' And the winner is...
PRINT
PRINT "From" + STR$(bestI) + ".." + LTRIM$(STR$(bestJ)) + ", sum:" + STR$(bestSum&)
PRINT
END[/syntax]

[xhantt]

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.

[Sterling Christensen]

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.

[xhantt]

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.

[Ryan]

lol Did you just challenge him to do your homework? :wink:

[Sterling Christensen]

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.

[na_th_an]

This is the typical backtracking with cut of branches problem

[xhantt]

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.