Created
January 3, 2017 14:00
-
-
Save airekans/4f6f973060bcc10802cecfc1423cb8d4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // O(n^3) | |
| double brute_force_max_subarray(const double* array, unsigned int size) | |
| { | |
| double max_sum = 0.0; | |
| for (unsigned int i = 0; i < size; ++i) { | |
| for (unsigned int j = i; j < size; ++j) { | |
| double tmp_sum = 0.0; | |
| for (unsigned int k = i; k <= j; ++k) { | |
| tmp_sum += array[k]; | |
| if (tmp_sum > max_sum) { | |
| max_sum = tmp_sum; | |
| } | |
| } | |
| } | |
| } | |
| return max_sum; | |
| } | |
| // O(n^2) | |
| double improved_brute_force_max_subarray(const double* array, unsigned int size) | |
| { | |
| double max_sum = 0.0; | |
| for (unsigned int i = 0; i < size; ++i) { | |
| double tmp_sum = 0.0; | |
| for (unsigned int j = i; j < size; ++j) { | |
| tmp_sum += array[j]; | |
| if (tmp_sum > max_sum) { | |
| max_sum = tmp_sum; | |
| } | |
| } | |
| } | |
| return max_sum; | |
| } | |
| // O(n lg(n)) | |
| double do_binary_max_subarray(const double* array, int l, int r) | |
| { | |
| if (l > r) { | |
| return 0.0; | |
| } else if (l == r) { | |
| return array[l] > 0.0? array[l] : 0.0; | |
| } | |
| unsigned int m = (l + r) / 2; | |
| double max_l = do_binary_max_subarray(array, l, m); | |
| double max_r = do_binary_max_subarray(array, m + 1, r); | |
| double cross_l = 0.0; | |
| double tmp_sum = 0.0; | |
| for (int i = m; i >= l; --i) { | |
| tmp_sum += array[i]; | |
| if (tmp_sum > cross_l) { | |
| cross_l = tmp_sum; | |
| } | |
| } | |
| double cross_r = 0.0; | |
| tmp_sum = 0.0; | |
| for (int i = m + 1; i <= r; ++i) { | |
| tmp_sum = array[i]; | |
| if (tmp_sum > cross_r) { | |
| cross_r = tmp_sum; | |
| } | |
| } | |
| return max(cross_l + cross_r, max(max_l, max_r)); | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment