5 ms·

The linear solution looks like it depends on the maximum subsequence being greater than zero. Is there a similar solution that can produce Integer results?

• aidenn0 16y ago
  Well it's linear time to find the maximum element of a sequence (which is equal to the maximum subsequence when all are non-positive), so you can by definition do both in linear time.
  • skew 16y ago
    If the empty subsequence is allowed, it's always possible to get at least zero.
    • aidenn0 16y ago
      Eh, one could argue that the sum of the empty subsequence is undefined.
  • DannoHung 16y ago
    Good point, I wasn't thinking.