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

Question

这是从面试测试中改写的问题:

Given is an array and integer K and integer J, each element in the array represents trees planted in a row, the value of the element is the amount of apples that tree has. K and J are the desired amount of consecutive trees that Karen an John want to pick respectively. Karen and Jon are not allowed to pick the same trees. Find the maximum number of apples that can be picked by Karen and John combined.

example:

array: 4 5 7 8 3 1

K: 3

J: 2

Karen picks the first 3 trees and John the next 2, total apples picked is 4 + 5 + 7 = 16 for Karen and 8 + 3 = 11 for John. Together this makes 27 which is the maximum, if John chose the final 2 trees instead of the 2 immediately following Karen he would have picked 4 apples instead of 11, which makes it the wrong solution.

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

Answer 1

好的，所以这可以用动态规划来解决。

• 首先，我们寻找约翰的苹果。因此，我们需要连续挑选 2 个苹果。让我们看一下示例:

4 5 7 8 3 1

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

0 9 12 15 15 15

• 现在，我们从右到左寻找 Karen 的苹果，因为我们已经从左到右找到了 John 的结果。现在，我们从右到左迭代 3 个连续的苹果。

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

• 我们选择 7 8 3。 John 的值为 9。所以总和是 7 + 8 + 3 + 9 = 27。我们将其记录在 max_sum 中。

• 然后我们用 5 7 8 等等，不断比较并记录在 max_sum 中。

• 注意对于 John 和从左到右<，您还需要从从右到左进行另一次迭代 为 Karen 处理 John 的数据，并相应地将值记录在 max_sum 中。

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

实现:(遵循相同的 LeetCode question )

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;
    }
}