I need to find the maximum possible weight of a package that can be achieved after any sequence of merge operations:

Below is the use case:

Consider n packages, where packageWeight[i] represents the weight of the ith package. You can combine the ith and (i 1)th package if packageWeight[i] < packageWeight[i 1], then discard the ith package. After this operation, the number of packages is reduced by 1, and the weight of the (i 1)th package increases by packageWeight[i]. you can merge the package any number of times.

Below is the example:

Input: [2, 9, 10, 3, 7]
Output: The weight of the heaviest package achievable after merging is 21.
Explanation: [2, 9, 10, 3, 7]

[2, 19, 3, 7]

[21, 3, 7]

[21, 10]

We cannot combine the packages anymore.

Below is the code I'm trying to run:

public static void main(String[] args) {
        SpringApplication.run(EmailServiceApiApplication.class, args);   
        int[] input =  {2, 9, 10, 3, 7};
        int result = getHeaviestPackage(input);
        System.out.print("the weight of heaviest package is "   result);
    }
    
    public static int getHeaviestPackage(int[] input) {
        int max  = input[0];
        for(int i = 0; i < input.length; i  ) {
            if(input[i] > max) {
                max = input[i];
            }
        }
        for(int i = 0; i < input.length; i  ) {
            if(input[i] == max) {
                if(input[i - 1] < input[i]) {
                    input[i] = input[i]   input[i - 1];
                }
            }
        }
        return 0;
    }

Can someone help me determine which data structure and algorithm I should use and how to solve the same?

CodePudding user response：

You are merging packages in the wrong order.

Merging two packages can make the new package too big to merge into a later one. The safe pair of packages to merge first is the very last mergable pair in the array, since the larger package on the right of that pair is already too large to be merged with anything that comes after it.

You just need to work from the end of the array toward the beginning.

public static int getHeaviest(int[] input) {
    int max = 0;
    for (int i = input.length - 1; i >= 0; --i) {
        if (input[i] < max) {
            max  = input[i]; // merge
        } else {
            max = input[i]; // too big to merge - this is the new max
        }
    }
    return max;
}