Maximum subarray O(n)

输入：数组arr
输出：maximum subarray，[begin, end)

1. 初始化result为- ∞，begin0 = 0, begin = begin0
2. 从前往后扫描，如果当前局部和大于result，更新result为局部和，更新begin = begin0, 更新end = i+1,
3. 如果局部和小于0，更新begin0 = i+1, 更新局部和为0

int maximum_subarray(int *arr, int len, int &begin, int &end)
{
    begin = 0;
    end = 1;
    int sum = 0, result = INT_MIN;
    int begin0 = 0;
    for (int i = 0; i < len; i++) {
        sum += arr[i];
        if (sum > result) {
            result = sum;
            begin = begin0;
            end = i + 1;
        }
        if (sum < 0) {
            begin0 = i + 1;
            sum = 0;
        }
    }
    return result;
}