Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Update definition of "Maximum subarray problem" #81

Open
funnydman opened this issue Dec 13, 2020 · 0 comments
Open

Update definition of "Maximum subarray problem" #81

funnydman opened this issue Dec 13, 2020 · 0 comments

Comments

@funnydman
Copy link

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.

@funnydman funnydman changed the title Wrong definition of "Maximum subarray problem" Update definition of "Maximum subarray problem" Dec 13, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant