max_subarray.cpp

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