【Lintcode】42. Maximum Subarray II

题目地址：

https://www.lintcode.com/problem/42/

给定一个长 n n n的数组 A A A，要求选取两段子数组，使得这两个子数组之总和最大。问这个最大和是多少。

求最大子段和是简单的，可以用动态规划来做。接下来可以开两个数组 l l l和 r r r， l [ i ] l[i] l[i]代表 A [ 0 : i ] A[0:i] A[0:i]的最大子段和是多少，而 r [ i ] r[i] r[i]代表 A [ i + 1 : n − 1 ] A[i+1:n-1] A[i+1:n−1]的最大子段和是多少，如果 f [ i ] f[i] f[i]是以 A [ i ] A[i] A[i]结尾的最大子段和是多少，那么就有 l [ i ] = max ⁡ { l [ i − 1 ] , f [ i ] } l[i]=\max\{l[i-1],f[i]\} l[i]=max{l[i−1],f[i]}这样可以类似把 r r r递推出来，然后求一下 max ⁡ 0 ≤ i < n − 1 { l [ i ] + r [ i + 1 ] } \max_{0\le i<n-1} \{l[i]+r[i+1]\} max0≤i<n−1​{l[i]+r[i+1]}即可。代码如下：

import java.util.List;

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(List<Integer> nums) {
        // write your code here
        int res = Integer.MIN_VALUE, n = nums.size(), cur = 0;
        int[] l = new int[n], r = new int[n];
        l[0] = cur = nums.get(0);
        for (int i = 1; i < n; i++) {
            cur = Math.max(nums.get(i), cur + nums.get(i));
            l[i] = Math.max(l[i - 1], cur);
        }
        r[n - 1] = cur = nums.get(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            cur = Math.max(nums.get(i), cur + nums.get(i));
            r[i] = Math.max(r[i + 1], cur);
        }
        
        for (int i = 0; i < n - 1; i++) {
            res = Math.max(res, l[i] + r[i + 1]);
        }
        
        return res;
    }
}
           

时空复杂度 O ( n ) O(n) O(n)。