最大子数组问题

看算法导论，其中第四章讲到了最大子数组问题，书上讲了暴力求解和分而治之两种方法，实现了这两种方法后，看课后习题说，其实还有另一种线性时间的解，就又自己动手写了起来。
底下，是对这三种解法的一个总结（代码也不难，我就废话不多，直接上代码了）。

暴力求解（O(n^2)）

#include <iostream>
#include <vector>
using namespace std;
typedef struct {
    int left;
    int right;
    int sum;
} ans_tuple;
ans_tuple find_max_subarray_violence(vector<int>& vec);
int main()
{
    int n;
    cin >> n;
    vector<int> vec;
    int elem;
    for (int i = 0; i < n; ++i) {
        cin >> elem;
        vec.push_back(elem);
    }
    ans_tuple a_t = find_max_subarray_violence(vec);
    cout << a_t.sum << " " << a_t.left << " " << a_t.right << endl;
    system("pause");
}

ans_tuple find_max_subarray_violence(vector<int>& vec) {
    int max_sum, this_sum;
    max_sum = this_sum = 0;
    int right, left;
    right = left = 0;
    vector<int> v_left;
    for (int index = 0; index < vec.size(); ++index) {
        this_sum = 0;
        for (int j = index; j < vec.size(); ++j) {
            this_sum += vec[j];
            if (this_sum > max_sum) {
                max_sum = this_sum;
                v_left.push_back(index);
                right = j;
            }
        }
    }
    if (max_sum == 0) {
        for (int j = 0; j < vec.size(); ++j) {
            if (vec[j] == 0) {
                return{ vec[j],vec[j],0 };
            }
        }
        return{ 0,vec.size() - 1,0 };
    }
    return{ v_left.size()-1,right,max_sum };
}

分而治之（O(nlgn)）

#include <iostream>
#include <vector>
using namespace std;
typedef struct {
    int left;
    int right;
    int sum;
} ans_tuple;
ans_tuple find_crossing_subarray(int A[], int low, int mid, int high);
ans_tuple find_max_subarray_conquer(int A[], int low, int high);
ans_tuple max_ans(ans_tuple &left_ans, ans_tuple &right_ans, ans_tuple& cross_ans);
int main()
{
    int n;
    cin >> n;
    int A[10000] = {};
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    ans_tuple a_t = find_max_subarray_conquer(A,0,n-1);
    cout << a_t.sum << " " << a_t.left << " " << a_t.right << endl;
    system("pause");
}
ans_tuple find_crossing_subarray(int A[],int low,int mid,int high) {
    int left_sum, right_sum, sum;
    left_sum = right_sum = sum = 0;
    int left,right;
    left = right = mid;
    for (int i = mid; i >= low; --i) {
        sum += A[i];
        if (sum > left_sum) {
            left_sum = sum;
            left = i;
        }
    }
    sum = 0;
    for(int j = mid + 1; j<=high;++j){
        sum += A[j];
        if (sum > right_sum) {
            right_sum = sum;
            right = j;
        }
    }
    return{ left,right,left_sum + right_sum };
}
ans_tuple find_max_subarray_conquer(int A[], int low, int high) {
    int mid;
    if (high == low) {
        return{ low,high,A[low] };
    }
    else {
        mid = (low + high) / 2;
    }
    ans_tuple left_ans = find_max_subarray_conquer(A, low, mid);
    ans_tuple right_ans = find_max_subarray_conquer(A, mid + 1, high);
    ans_tuple cross_ans = find_crossing_subarray(A, low, mid, high);
    ans_tuple ans = max_ans(left_ans, right_ans, cross_ans);
    if (ans.sum == 0) {
        for (int j = 0; j <= high; ++j) {
            if (A[j] == 0) {
                return{ j,j,0 };
            }
        }
        return{ 0,high,0 };
    }
    return ans;
    
}
ans_tuple max_ans(ans_tuple &left_ans, ans_tuple &right_ans, ans_tuple& cross_ans) {
    if (left_ans.sum >= right_ans.sum && left_ans.sum >= cross_ans.sum) {
        return left_ans;
    }
    else if (right_ans.sum >= left_ans.sum && right_ans.sum >= cross_ans.sum) {
        return right_ans;
    }
    else return cross_ans;
}

线性时间解（O(n)）

#include <iostream>
#include <vector>
using namespace std;
typedef struct {
    int left;
    int right;
    int sum;
} ans_tuple;

ans_tuple find_max_subarray_linear(vector<int>& vec) {
    int this_sum, max_sum;
    this_sum = max_sum = 0;
    int left, right;
    right = left = 0;
    vector<int> v_left;
    v_left.push_back(0);
    for (int i = 0; i < vec.size(); ++i) {
        this_sum += vec[i];
        if (this_sum > max_sum) {
            max_sum = this_sum;
            right = i;
        }
        else if (this_sum < 0) {
            this_sum = 0;
            if (i < vec.size() - 1) {
                v_left.push_back(i + 1);
            }
        }
    }
    if (max_sum == 0) {
        for (int j = 0; j < vec.size(); ++j) {
            if (vec[j] == 0) {
                return{ j,j,0 };
            }
        }
        return{ 0,vec.size()-1,0 };
    }
    for (int i = v_left.size()-1; i >= 0; --i) {
        if (v_left[i] <= right) {
            left = v_left[i];
            break;
        }
    }
        return{ left,right,max_sum };
}
int main()
{
    int n;
    cin >> n;
    vector<int> vec;
    int elem;
    for (int i = 0; i < n; ++i) {
        cin >> elem;
        vec.push_back(elem);
    }
    ans_tuple a_t = find_max_subarray_linear(vec);
    cout << a_t.sum << " " << a_t.left << " " << a_t.right << endl;
    system("pause");
}