Definition. Given the real vector x [n], compute the maximum sum found in any contiguous subvector. example:If the input vector is 31 -41 59 26 -53 58 97 -93 -23 84 then the program returns the sum of x[2..6], or 187.
In the year of '86 John Bentley published the folowing comparisons for cubic algorithm and linear algorithm:
10 0 seconds 0 s
100 0 s 0 s
1000 0.873 s 0 s
10.000 14.19 minutes 0 s
100.000 - 0 s
1.000.000 - 0.015 s
10.000.000 - 0.094 s
100.000.000 - 0.983 s
