Task

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.



An empty subsequence is considered to have the sum of   0;   thus if all elements are negative, the result must be the empty sequence.




' FB 1.05.0 Win64
 
Dim As Integer seq(10) = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1}
Dim As Integer i, j, sum, maxSum, first, last
 
maxSum = 0
 
For i = LBound(seq) To UBound(seq)
  sum = 0
  For j = i To UBound(seq)
    ' only proper sub-sequences are considered
    If i = LBound(seq) AndAlso j = UBound(seq) Then Exit For
    sum += seq(j)
    If sum > maxSum Then
      maxSum = sum
      first = i
      last = j 
    End If
  Next j
Next i
 
If maxSum > 0 Then
  Print "Maximum subsequence is from indices"; first; " to"; last
  Print "Elements are : ";
  For i = first To last
    Print seq(i); " ";
  Next
  Print
  Print "Sum is"; maxSum
Else
  Print "Maximum subsequence is the empty sequence which has a sum of 0"
End If
 
Print
Print "Press any key to quit"
Sleep