Greatest subsequential sum: Difference between revisions

=={{header|C sharp|C#}}==

'''The challange'''

<lang csharp>using System;

namespace Tests_With_Framework_4

{

class Program

{

static void Main(string[] args)

{

int[] integers = { -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 }; int length = integers.Length;

int maxsum, beginmax, endmax, sum; maxsum = beginmax = sum = 0; endmax = -1;

for (int i = 0; i < length; i++)

{

sum = 0;

for (int k = i; k < length; k++)

{

sum += integers[k];

if (sum > maxsum)

{

maxsum = sum;

beginmax = i;

endmax = k;

}

}

}

for (int i = beginmax; i <= endmax; i++)

Console.WriteLine(integers[i]);

Console.ReadKey();

}

}

}</lang>

=={{header|Component Pascal}}==

Works with BlackBox Component Builder

<lang oberon2>

MODULE OvctGreatestSubsequentialSum;

IMPORT StdLog, Strings, Args;

PROCEDURE Gss(iseq: ARRAY OF INTEGER;OUT start, end, maxsum: INTEGER);

VAR

i,j,sum: INTEGER;

BEGIN

i := 0; maxsum := 0; start := 0; end := -1;

WHILE i < LEN(iseq) - 1 DO

sum := 0; j := i;

WHILE j < LEN(iseq) -1 DO

INC(sum ,iseq[j]);

IF sum > maxsum THEN

maxsum := sum;

start := i;

end := j

END;

INC(j);

END;

INC(i)

END

END Gss;

PROCEDURE Do*;

VAR

p: Args.Params;

iseq: POINTER TO ARRAY OF INTEGER;

i, res, start, end, sum: INTEGER;

BEGIN

Args.Get(p); (* Get Params *)

NEW(iseq,p.argc);

(* Transform params to INTEGERs *)

FOR i := 0 TO p.argc - 1 DO

Strings.StringToInt(p.args[i],iseq[i],res)

END;

Gss(iseq,start,end,sum);

StdLog.String("[");

FOR i := start TO end DO

StdLog.Int(iseq[i]);

IF i < end THEN StdLog.String(",") END

END;

StdLog.String("]=");StdLog.Int(sum);StdLog.Ln;

END Do;

END OvctGreatestSubsequentialSum.

</lang>

Execute: <br/>

<pre>

[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -2 3 5 6 -2 -1 4 -4 2 -2 ~

[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -5 -3 ~

</pre>

{{out}}

<pre>

[ 3, 5, 6, -2, -1, 4]= 15

[]= 0

</pre>

=={{header|E}}==

This implementation tests every combination, but it first examines the sequence to reduce the number of combinations tried: We need not consider beginning the subsequence at any point which is not the beginning, or a change from negative to positive. We need not consider ending the subsequence at any point which is not the end, or a change from positive to negative. (Zero is moot and treated as negative.)

This algorithm is therefore <math>O(nm^2)</math> where <math>n</math> is the size of the sequence and <math>m</math> is the number of sign changes in the sequence. [[User:Kevin Reid|I]] think it could be improved to <math>O(n + m^2)</math> by recording the positive and negative intervals' sums during the initial pass and accumulating the sum of those sums in the inner for loop.

<code>maxSubseq</code> returns both the maximum sum found, and the interval of indexes which produces it.

<lang e>pragma.enable("accumulator")

def maxSubseq(seq) {

def size := seq.size()

# Collect all intervals of indexes whose values are positive

def intervals := {

var intervals := []

var first := 0

while (first < size) {

var next := first

def seeing := seq[first] > 0

while (next < size && (seq[next] > 0) == seeing) {

next += 1

}

if (seeing) { # record every positive interval

intervals with= first..!next

}

first := next

}

intervals

}

# For recording the best result found

var maxValue := 0

var maxInterval := 0..!0

# Try all subsequences beginning and ending with such intervals.

for firstIntervalIx => firstInterval in intervals {

for lastInterval in intervals(firstIntervalIx) {

def interval :=

(firstInterval.getOptStart())..!(lastInterval.getOptBound())

def value :=

accum 0 for i in interval { _ + seq[i] }

if (value > maxValue) {

maxValue := value

maxInterval := interval

}

}

}

return ["value" => maxValue,

"indexes" => maxInterval]

}</lang>

<lang e>def seq := [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]

def [=> value, => indexes] := maxSubseq(seq)

println(`$\

Sequence: $seq

Maximum subsequence sum: $value

Indexes: ${indexes.getOptStart()}..${indexes.getOptBound().previous()}

Subsequence: ${seq(indexes.getOptStart(), indexes.getOptBound())}

`)</lang>

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Python}}

{{works with|Rakudo|2016.12}}

<lang perl6>sub max-subseq (*@a) {

my ($start, $end, $sum, $maxsum) = -1, -1, 0, 0;

for @a.kv -> $i, $x {

$sum += $x;

if $maxsum < $sum {

($maxsum, $end) = $sum, $i;

}

elsif $sum < 0 {

($sum, $start) = 0, $i;

}

}

return @a[$start ^.. $end];

}</lang>

Another solution, not translated from any other language:

For each starting position, we calculate all the subsets starting at that position.

They are combined with the best subset ($max-subset) from previous loops, to form (@subsets).

The best of those @subsets is saved at the new $max-subset.

Consuming the array (.shift) allows us to skip tracking the starting point; it is always 0.

The empty sequence is used to initialize $max-subset, which fulfils the "all negative" requirement of the problem.

<lang perl6>sub max-subseq ( *@a ) {

my $max-subset = ();

while @a {

my @subsets = [\,] @a;

@subsets.push: $max-subset;

$max-subset = @subsets.max: { [+] .list };

@a.shift;

}

return $max-subset;

}

max-subseq( -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ).say;

max-subseq( -2, -2, -1, 3, 5, 6, -1, 4, -4, 2, -1 ).say;

max-subseq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).say;</lang>

{{out}}

<pre>

(3 5 6 -2 -1 4)

(3 5 6 -1 4)

()</pre>