65 lines
1.8 KiB
Plaintext
65 lines
1.8 KiB
Plaintext
_rndlen = 01 //BOOL: is sequence length random or fixed
|
|
_maxlen = 14 //Length of each/longest sequence
|
|
_maxVal = 20 //Largest number (pos or neg) in sequence
|
|
_repeat = 25 //Number of sequences to evaluate
|
|
|
|
void local fn maxSubSequence
|
|
int i, j, seq(_maxlen), ndx(_maxlen + 1),sum(_maxlen)
|
|
int grp, maxSum, maxNdx, maxEnd, tot, iterations = _repeat
|
|
|
|
while iterations
|
|
iterations--
|
|
|
|
// Create random sequence
|
|
int count = (_rndlen) ? rnd(_maxlen) : _maxlen
|
|
for i = 1 to count
|
|
seq(i) = rnd(_maxVal * 2 + 1) - _maxVal - 1
|
|
next
|
|
|
|
// Determine maximum sub-sequence
|
|
bool isNeg = yes : grp = 0 : sum(0) = 0 : ndx(0) = 0
|
|
maxSum = 0 : maxNdx = 0 : maxEnd = 0
|
|
|
|
for i = 1 to count // Merge array into groups of like signs
|
|
if (seq(i) < 0) <> isNeg // If change of sign...
|
|
grp ++ // Start new group
|
|
isNeg = yes - isNeg
|
|
ndx(grp) = i
|
|
sum(grp) = 0
|
|
end if
|
|
sum(grp) += seq(i)
|
|
next
|
|
ndx(grp + 1) = 0
|
|
|
|
for i = 1 to grp step 2 // Determine max sub-sequence
|
|
j = i : tot = sum(j)
|
|
do
|
|
if tot > maxSum
|
|
maxSum = tot
|
|
maxNdx = ndx(i)
|
|
maxEnd = ndx(j + 1)
|
|
end if
|
|
j += 2 : tot += sum(j - 1) + sum(j) // add next neg & pos groups
|
|
until j > grp
|
|
next
|
|
|
|
// Print result
|
|
print @" Sum = "; maxSum, " {";
|
|
for i = 1 to count
|
|
if i == maxNdx then text ,,, _zCyan
|
|
if i == maxEnd then text ,,, fn ColorClear
|
|
print " "; seq(i); " ";
|
|
next
|
|
text ,,, fn ColorClear
|
|
print "}"
|
|
|
|
wend
|
|
end fn
|
|
|
|
window 1, @"Maximum subsequence"
|
|
CFTimeInterval t : t = fn CACurrentMediaTime
|
|
fn maxSubSequence
|
|
printf @"\n %d random sequences created, solved, and printed in %.3f sec.",_repeat,1*(fn CACurrentMediaTime - t)
|
|
|
|
handleevents
|