两个子数组最大的累加和

问题

给定一个数组,其中当然有很多的子数组,在所有两个子数组的组合中,找到相 加和最大的一组,要求两个子数组无重合的部分。最后返回累加和.
时间复杂度达到 O(N)

思路

在解决这道题目之前，首先搞清楚一个问题： 子数组最大的累加和 ；单个子数组最大的累加和为本题的算法原型。

如何将本题转换到算法原型上去呢？两个子数组肯定是不相容的。我们人为地将数组划分成左右两个部分，分别对两个子数组求最大累加和，转型成功！该问题得到解决

要求两个子数组最大的累加和，我们一定要枚举出所有情况，最终求得和值最大的那个。遍历一遍数组，每个位置处将数组划分成两部分。这个过程的时间复杂度已经是O(N)。要完成题目要求的O(N)复杂度，我们计算子数组的最大累加和必须是O(1)。
如何解决？很简单。用空间换时间，先计算出各位置处的最大累加和，用数组保存起来。遍历到该位置时，直接从数组中取数即可。

算法实现：
定义两个数组L和R，L数组保存记录各位置左侧子数组最大累加和(0到当前位置)，R数组保存记录各位置右侧子数组最大累加和(当前位置到最后一个元素)。由之前容器盛水问题的解法3的经验，直接干掉L数组，一个R数组便可解决问题

核心代码

int maxSum(int *arr)
{
    if (arr == NULL || length < 2)
    {
        return 0;
    }
    int cur = 0;
    int lmax = arr[0];
    int R[length];
    R[length - 1] = arr[length - 1];
    for (int i = length - 2; i >= 0; i--)
    {
        if (cur < 0)
        {
            cur = 0;
        }
        cur += arr[i];
        R[i] = max(R[i + 1], cur);
    }
    //初始化
    int res  = arr[0] + R[1];
    for (int i = 1; i < length - 1; i++)
    {
        if (cur < 0)
        {
            cur = 0;
        }
        cur += arr[i];
        lmax = max(lmax, cur);
        res = max(res, lmax + R[i + 1]);
    }
    return res;
}

由于R数组是单调递减的，R[i + 1]即是当前从右往左最大的元素
R[i] = max(R[i + 1], cur);