Maximum subarray problem. Brute Force, Divide and Conquer, Kadane's Algorithm
More info: https://www.mycertnotes.com/az/maximum-subarray-problemi-kadane-alqoritmi/
The following stock problem is given in Introduction to Algorithms book (on page 68), you can solve it using "Maximum-subarray":
It is shown three solution for maximum-subarray problem in this project:
| N | Algorithm | Time complexity |
|---|---|---|
| 1 | Brute-force | O(n^2) |
| 2 | Divide and Conquer | O(nlogn) |
| 3 | Kadane's Algorithm | O(n) |
I compared these three solutions in my local machine and result was (duration is given with milliseconds):
| Array length | Brute-force | Divide and Conquer | Kadane's Algorithm |
|---|---|---|---|
| 1000 | 13 ms | 2 ms | 1 ms |
| 1_000_000 | 646535 ms | 115 ms | 9 ms |
