Given an array A consisting of N integers denoting the number of coins on each box in the row, and integers K and L denoting, respectively, the number of boxes that robo1 and robo2 can choose when collecting, returns the maximum number of coins that can be collected by them, or -1 if there are no such intervals.

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.

I have written below function to collect max coins.

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

The above solution is working fine for the given cases.

But I feel my solution has few problems

1. Not optimistic/Less performant
2. Failing on edge cases
3. Not following any algorithmic approach

Please help to point out. What is the right approaches/algorithms available to solve this in more efficient manner.

CodePudding user response：

You can solve the problem with a sliding window algorithm. The window's length should be K L. Imagine robo1 leading, and robo2 following behind as they march across the array.

As the window moves you need to update separate sums for each robot: sum1 and sum2. You also need to keep track of the best sum seen by the trailing robot: best2, and the best combined sum: bestCombined.

After each window move, update the best results:

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

When the sliding window reaches the end of the array, bestCombined is one of two possible answers. Swap the robots, and run the algorithm again to find the other possible answer.

Here's a sample run of the algorithm.
First with robo1 leading (blue) and robo2 following (red):

Then with robo2 leading, and robo1 following:

The best combined score is 24 which is achieved with robo2 leading.