Skip to content

Update definition of "Maximum subarray problem" #81

@funnydman

Description

@funnydman

Maximum subarray problem is a well known problem and has specified properties, e.g.

  1. If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
  2. If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted).
  3. Several different sub-arrays may have the same maximum sum.

The second property is broken, array containing only negative numbers returns 0, instead of correct result. There is a leetcode task that also assumes compliance with this rule.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions