寻找总和最大的非重叠子数组对

Question

这是面试测试中的问题，释义如下：

给定一个数组和整数K和整数J，数组中的每个元素代表一排种植的树，元素的值是这棵树有苹果的数量。K 和 J 分别是 Karen 和 John 想要采摘的连续树的数量。凯伦和乔恩不被允许采摘同一棵树。求凯伦和约翰总共可以采摘的苹果的最大数量。

例子：

数组：4 5 7 8 3 1

克：3

杰：2

凯伦 (Karen) 摘了前 3 棵树，约翰 (John) 摘了后 2 棵，凯伦 (Karen) 摘了 4 + 5 + 7 = 16 个苹果，约翰 (John) 摘了 8 + 3 = 11 个苹果。总共有 27 个，这是最大值，如果约翰选择了最后的 2 棵树而不是紧随凯伦之后的 2 棵树，他就会选择 4 个苹果而不是 11 个，这使得它是错误的解决方案。

理论上我有一种方法可以解决这个问题，但它涉及测试凯伦和约翰之间苹果的每一个可能的总和，这使得对于庞大的数据集来说过于复杂。我将如何解决这个问题？

Answer 1

好的，这可以通过动态规划来解决。

• 首先，我们寻找约翰的苹果。所以，我们需要采摘2连续的苹果。让我们看一下例子：

4 5 7 8 3 1

• 好的，我们从左向右移动，并跟踪 size 值的连续性中的最大可能值2。所以，我们的数组看起来像，

0 9 12 15 15 15

• 现在，我们从右到左查找凯伦的苹果，因为我们已经从左到右找到了约翰的结果。3现在，我们从右到左迭代连续的苹果。

• 我们从John is开始，8 3 1之前的值是。所以总和是. 我们将其记录在变量中。8128 + 3 + 1 + 12 = 24max_sum

• 我们一起去7 8 3。的价值John是9. 所以总和是7 + 8 + 3 + 9 = 27. 我们将其记录在max_sum.

• 然后我们继续进行5 7 8比较并记录在max_sum.

• 注意，您还需要对 John 处理的数据进行另一次right to leftforJohn和left to rightfor迭代Karen，并相应地记录值max_sum。

• 打印max_sum在最后。时间复杂度为O(n)，空间复杂度为O(n)。

实现：（遵循相同的LeetCode 问题）

class Solution {
    public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        int max_val = 0;
        int[] subs = new int[A.length];
        int sum = 0;
        for(int i=0;i<A.length;++i){
            sum += A[i];
            if(i == M-1) subs[i] = sum;
            else if(i > M-1){
                sum = sum - A[i-M];
                subs[i] = Math.max(subs[i-1],sum);
            }
        }
        sum = 0;
        for(int i=A.length-1,j=L-1;i>0;--i,--j){
            sum += A[i];
            if(j <= 0){
                if(j < 0) sum -= A[i+L];                
                max_val = Math.max(max_val,subs[i-1] + sum);
            }
        }

        sum = 0;
        Arrays.fill(subs,0);

        for(int i=A.length-1,j=M-1;i>=0;--i,--j){
            sum += A[i];
            if(j == 0) subs[i] = sum;
            else if(j < 0){
                sum -= A[i+M];
                subs[i] = Math.max(subs[i+1],sum);
            }            
        }
        sum = 0;
        for(int i=0,j=0;i<A.length-1;++i,++j){
            sum += A[i];
            if(j >= L-1){
                if(j >= L) sum -= A[i-L];
                max_val = Math.max(max_val,subs[i+1] + sum);
            } 
        }



        return max_val;
    }
}