Find Maximum Subarray in C++11

find-maximum-subarray_CMakeLists.txt

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)

find-maximum-subarray_FindMaximumSubarray.cpp

//
// 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));
}

find-maximum-subarray_FindMaximumSubarray.h

//
// 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

find-maximum-subarray_main.cpp

#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;
}