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.




      DIM A%(11) : A%() = 0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2
      PRINT FNshowarray(A%()) " -> " FNmaxsubsequence(A%())
      DIM B%(10) : B%() = -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1
      PRINT FNshowarray(B%()) " -> " FNmaxsubsequence(B%())
      DIM C%(4) : C%() = -1, -2, -3, -4, -5
      PRINT FNshowarray(C%()) " -> " FNmaxsubsequence(C%())
      END
 
      DEF FNmaxsubsequence(a%())
      LOCAL a%, b%, i%, j%, m%, s%, a$
      a% = 1
      FOR i% = 0 TO DIM(a%(),1)
        s% = 0
        FOR j% = i% TO DIM(a%(),1)
          s% += a%(j%)
          IF s% > m% THEN
            m% = s%
            a% = i%
            b% = j%
          ENDIF
        NEXT
      NEXT i%
      IF a% > b% THEN = "[]"
      a$ = "["
      FOR i% = a% TO b%
        a$ += STR$(a%(i%)) + ", "
      NEXT
      = LEFT$(LEFT$(a$)) + "]"
 
      DEF FNshowarray(a%())
      LOCAL i%, a$
      a$ = "["
      FOR i% = 0 TO DIM(a%(),1)
        a$ += STR$(a%(i%)) + ", "
      NEXT
      = LEFT$(LEFT$(a$)) + "]"