pllk / cphb

Competitive Programmer's Handbook
2.9k stars 347 forks source link

Update definition of "Maximum subarray problem" #81

Open funnydman opened 3 years ago

funnydman commented 3 years ago

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.