在 2 个连续的时间间隔内从阵列中收集最大硬币

Question

给定一个由 N 个整数组成的数组 A，表示每个 box 上 coins 的个数行，整数 K 和 L 分别表示 robo1 and robo2 可以放置的框数收集时选择，returns他们可以收集的最大硬币数量，或-1 如果没有这样的间隔。

For example, given A = [6, 1, 4, 6, 3, 2, 7, 4], K = 3, L = 2, your function should return 24, because robo1 can choose boxes 3 to 5 and collect 4 + 6 + 3 = 13 coins, and robo2 can choose boxes 7 to 8 and collect 7 +4 = 11 coins. Thus, they will collect 13 + 11 = 24 coins in total, and that is the maximum number that can be achieved.

Given A = [10, 19, 15], K = 2, L = 2, your function should return -1, because it is not possible for robo1 and robo2 to choose two disjoint intervals.

我写了下面的函数来收集最大硬币。

public static int getMaxCoins(int[] A, int K, int L) {

    if(A.length<K+L)
        return -1;
    
    int highest = 0;
    int lowest = 0;

    if(K>L){
        highest = K;
        lowest = L;
    }
    
    int robo1Coins = 0;       
    int remainingArray[] = null;
    int part1[];
    int part2[];
    
    int robo2Coins = 0;
    
    for(int i=0;i+highest<=A.length;i++){
        int[] sub = Arrays.copyOfRange(A, i, i+highest);
        int count = IntStream.of(sub).sum();
        if(count>robo1Coins) {
            robo1Coins = count;
            part1 = Arrays.copyOfRange(A, 0, i);
            part2 = Arrays.copyOfRange(A, i+highest, A.length);
            remainingArray = IntStream.concat(Arrays.stream(part1), Arrays.stream(part2)).toArray();
        }            
    }
    
    for(int i=0;i+lowest<=remainingArray.length;i++){
        int[] sub = Arrays.copyOfRange(remainingArray, i, i+lowest);
        int count = IntStream.of(sub).sum();
        if(count>robo2Coins) {
            robo2Coins = count;
        }            
    }
    
    System.out.println("Robo1 Coins - "+robo1Coins+" Robo2 Coins-"+robo2Coins);

return robo1Coins+robo2Coins;
}

上述解决方案在给定情况下运行良好。

But I feel my solution has few problems

Not optimistic/Less performant

Failing on edge cases

Not following any algorithmic approach

请帮忙指出。什么是正确的 approaches/algorithms 可以更有效地解决这个问题。

Answer 1

你可以用滑动window算法来解决这个问题。 window 的长度应该是 K+L。想象一下 robo1 领先，robo2 跟随在他们穿过阵列时。

随着 window 的移动，您需要为每个机器人更新单独的总和：sum1 和 sum2。您还需要跟踪尾部机器人看到的最佳总和：best2，以及最佳组合总和：bestCombined.

每次 window 移动后，更新最佳结果：

best2=max(best2, sum2) 
bestCombined=max(bestCombined, best2+sum1)

当滑动window到达数组末尾时，bestCombined是两种可能的答案之一。交换机器人，然后运行算法再次找到其他可能的答案。

这是算法的示例运行。
首先是 robo1 领先（蓝色）和 robo2 跟随（红色）：

然后robo2在前，robo1在后：

最好的综合得分是 24，这是在 robo2 领先的情况下取得的。

在 2 个连续的时间间隔内从阵列中收集最大硬币

Collect Max Coins From An Array In 2 Consecutive Intervals

java

algorithm

math

data-structures