[CareerCup] 17.8 Contiguous Sequence with Largest Sum 连续子序列之和最大

int get_max_sum(vector<int> nums) {
    int res = INT_MIN, sum = INT_MIN;
    for (auto a : nums) {
        sum = max(sum + a, a);
        res = max(res, sum);
    }
    return res;
}

int helper(vector<int> nums, int left, int right) {
    if (left >= right) return nums[left];
    int mid = left + (right - left) / 2;
    int lmax = helper(nums, left, mid - 1);
    int rmax = helper(nums, mid + 1, right);
    int mmax = nums[mid], t = nums[mid];
    for (int i = mid - 1; i >= left; --i) {
        t += nums[i];
        mmax = max(mmax, t);
    }
    t = mmax;
    for (int i = mid + 1; i <= right; ++i) {
        t += nums[i];
        mmax = max(mmax, t);
    }
    return max(mmax, max(lmax, rmax));
}

int get_max_sum(vector<int> nums) {
    return helper(nums, 0, nums.size() - 1);
}