Created
December 5, 2017 12:12
-
-
Save filosofisto/0bf5cffe0f064893ca382bfcd89a63af to your computer and use it in GitHub Desktop.
Find Maximum Subarray in C++11
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
cmake_minimum_required(VERSION 3.9) | |
project(find_maximum_subarray) | |
set(CMAKE_CXX_STANDARD 11) | |
add_executable(find_maximum_subarray main.cpp FindMaximumSubarray.cpp FindMaximumSubarray.h) |
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
// | |
// Created by eduardo on 12/3/17. | |
// | |
#include "FindMaximumSubarray.h" | |
FindMaximumSubarray::FindMaximumSubarray() { | |
} | |
FindMaximumSubarray::~FindMaximumSubarray() { | |
} | |
unique_ptr<FindMaximumSubarrayResult> FindMaximumSubarray::find_max_subarray(int *array, int low, int high) { | |
if (high == low) | |
return unique_ptr<FindMaximumSubarrayResult>(new FindMaximumSubarrayResult(low, high, array[low])); | |
int mid = (low + high)/2; | |
unique_ptr<FindMaximumSubarrayResult> left = find_max_subarray(array, low, mid); | |
unique_ptr<FindMaximumSubarrayResult> right = find_max_subarray(array, mid + 1, high); | |
unique_ptr<FindMaximumSubarrayResult> cross = find_max_crossing_subarray(array, low, mid, high); | |
if (left->sum >= right->sum && left->sum >= cross->sum) | |
return unique_ptr<FindMaximumSubarrayResult>(new FindMaximumSubarrayResult(left->low, left->high, left->sum)); | |
else if (right->sum >= left->sum && right->sum >= cross->sum) | |
return unique_ptr<FindMaximumSubarrayResult>(new FindMaximumSubarrayResult(right->low, right->high, right->sum)); | |
else | |
return unique_ptr<FindMaximumSubarrayResult>(new FindMaximumSubarrayResult(cross->low, cross->high, cross->sum)); | |
} | |
unique_ptr<FindMaximumSubarrayResult> FindMaximumSubarray::find_max_crossing_subarray(int *array, int low, int mid, int high) { | |
int left_sum = INT_MIN; | |
int sum = 0; | |
int max_left; | |
for (int i = mid; i >= low; i--) { | |
sum += array[i]; | |
if (sum > left_sum) { | |
left_sum = sum; | |
max_left = i; | |
} | |
} | |
int right_sum = INT_MIN; | |
sum = 0; | |
int max_right; | |
for (int j = mid+1; j <= high; j++) { | |
sum += array[j]; | |
if (sum > right_sum) { | |
right_sum = sum; | |
max_right = j; | |
} | |
} | |
return unique_ptr<FindMaximumSubarrayResult>(new FindMaximumSubarrayResult(max_left, max_right, left_sum+right_sum)); | |
} |
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
// | |
// Created by eduardo on 12/3/17. | |
// | |
#ifndef FIND_MAXIMUM_SUBARRAY_FINDMAXIMUMSUBARRAY_H | |
#define FIND_MAXIMUM_SUBARRAY_FINDMAXIMUMSUBARRAY_H | |
#include <climits> | |
#include <bits/unique_ptr.h> | |
using namespace std; | |
struct FindMaximumSubarrayResult | |
{ | |
int low; | |
int high; | |
int sum; | |
FindMaximumSubarrayResult(int low, int high, int sum): low(low), high(high), sum(sum) { } | |
}; | |
class FindMaximumSubarray { | |
public: | |
FindMaximumSubarray(); | |
~FindMaximumSubarray(); | |
unique_ptr<FindMaximumSubarrayResult> find_max_subarray(int *array, int low, int high); | |
private: | |
unique_ptr<FindMaximumSubarrayResult> find_max_crossing_subarray(int *array, int low, int mid, int high); | |
}; | |
#endif //FIND_MAXIMUM_SUBARRAY_FINDMAXIMUMSUBARRAY_H |
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
#include <iostream> | |
#include "FindMaximumSubarray.h" | |
using namespace std; | |
int main() { | |
cout << "Find Maximum Subarray" << endl; | |
int array[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 }; | |
FindMaximumSubarray finder; | |
unique_ptr<FindMaximumSubarrayResult> result = finder.find_max_subarray(array, 0, (int) sizeof(array) / sizeof(array[0]) - 1); | |
cout << "low: " << result->low << endl; | |
cout << "high: " << result->high << endl; | |
cout << "sum: " << result->sum << endl; | |
cout << "{ "; | |
for (int i = result->low; i <= result->high; i++) { | |
cout << array[i]; | |
if (i < result->high) | |
cout << ", "; | |
} | |
cout << " }" << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment