Find longest sum for array and given days

Issue

A hiker is planning a multi-day trek through the mountains. There are n trails, each with a certain length, given as a list, trails, that need to be covered in the same order given in the list. The hiker wants to achieve a new world record by completing the trek in record number of days. The hiker also wants to cover at least one trail on each day and ensure that the sum of the lengths of the longest trail covered on each day is the minimum possible. Find this minimum sum.

For example, say there are n =6 trails with lengths trails = [10,5,9,3,8,15], and record = 2. Then, the hiker covers the first trail on the first day, so the longest trail length is 10, and the remaining trails on the second day, so the longest trail on the second day is of length max(5,9,3,8,15) = 15. The sum of the lengths of the longest trails on all the days is 10 + 15 = 25. Return 25.

Other Examples:

array = [150, 200, 400, 350, 250] and record = 3

Ans:
Cover the first trail on day 1, the second on day 2, and the remaining on day 3.
The total is 150 + 200 + max(400, 350, 250) = 750

Example:

array = [78, 45, 12, 56, 85, 45], record=1

Ans:

Covers all the trails in one day.

Output = 85

**Constraint: **

n is of size 1 to 300 record is of size 1 to 300 array elements holds values 1 to 10^5 Result of the program is an int, so no need to use long

Here is my approach:

Pick first (record-1) items from array and add them to result, next get the maximum item from (record to array.length) and add that to result.

Based on the instructions I have written the code. This was asked during an interview one month back in hackerrank, this code solved only 10 out of 15 test cases. The remaining cases failed saying wrong output and they are hidden cases.

Is there anything I am missing here that is causing the test cases fail? I tried using long variables also but there is no improvement in score.

Update:

Using dynamic programming:

public static void main(String[] args) {
        solve(new int[]{1000, 500, 2000, 8000, 1500}, 3); // correct result : 9500
        solve(new int[]{3000, 1000, 4000}, 2); // correct result : 7000
        solve(new int[]{190, 200, 450, 499, 358, 160}, 3); // correct result : 849
    }
    
    public static void solve(int[] x, int D) {
        int T = x.length; // Number of trails
        
        int[][][] v = new int[T + 1][D + 1][T + 1];
        int[][][] z = new int[T + 1][D + 1][T + 1];
        
        // Dynamic programming
        for (int t = 1; t <= T; t++) {
            for (int d = 1; d <= Math.min(D, t); d++) {
                for (int n = 1; n <= t; n++) {
                    if (t == 1 && d == 1) {
                        v[t][d][n] = x[t - 1];
                        z[t][d][n] = x[t - 1];
                    } else {
                        x[t - 1] = x[t - 1]; // Length of current trail
                        
                        if (d == 1) {
                            z[t][d][n] = Math.max(z[t - 1][d][n - 1], x[t-1]);
                            v[t][d][n] = v[t - 1][d][n - 1] - z[t - 1][d][n - 1] + z[t][d][n];
                        } else {
                            int maxLastTrail = Math.max(z[t - 1][d][n - 1], x[t-1]);
                            z[t][d][n] = maxLastTrail;
                            v[t][d][n] = v[t - 1][d][n - 1] - z[t - 1][d][n - 1] + z[t][d][n];
                        }
                    }
                }
            }
        }
        
        // Finding the optimal value
        int optimalValue = Integer.MAX_VALUE;
        for (int n = 1; n <= T; n++) {
            optimalValue = Math.min(optimalValue, v[T][D][n]);
        }
        
        //System.out.println("Optimal value: " + optimalValue);
        
        // Backtracking to construct optimal solution
        int daysLeft = D;
        int trailsLeft = T;
        int lastTrails = -1;
        
        for (int n = T; n >= 1; n--) {
            if (v[trailsLeft][daysLeft][n] == optimalValue) {
                lastTrails = n;
                break;
            }
        }
        
        List<Integer> hikePlan = new ArrayList<>();
        for (int t = T; t >= 1 && daysLeft >=0 && lastTrails >=0; t--) {
            if (v[t][daysLeft][lastTrails] != optimalValue) {
                trailsLeft = t + 1;
                daysLeft--;
                lastTrails--;
                hikePlan.add(trailsLeft);
            }
        }
        
        Collections.reverse(hikePlan);
        
        // Printing the hike plan
        int result = 0;
        for(int e : hikePlan) {
            result += x[e-1];
        }
        System.out.println(result);
    }
}

I tried to implement the solution provided by Cary Swoveland, but I am not clear where I did mistake, I am getting wrong output.

For input {3000, 1000, 4000}, 2 correct result is 7000 but I am getting 5000. Similarly for input {190, 200, 450, 499, 358, 160}, 3, correct output is 849 but getting 518. For input {150, 200, 400, 350, 250}, 3, correct output is 750 but I am getting 600.

Solution

The approach with dynamic programming seems the right way to go. I would use a memoization table with only two dimensions, where the y-coordinate represents the number of partitions, and the x coordinate the index where the subarray under consideration starts (and extends to the end). The value found in the table should provide the optimal solution (minimum of sum of maxima) for the denoted subarray and number of partitions.

If you take a bottom-up approach you would:

• Define 0 for when the number of partitions is zero: nothing to do. Zero is actually not a valid value for the number of partitions, but it will serve for the rest of the algorithm.
• Define the results for when the number of partitions is one: in that case the maximum of the subarray must be stored. This can be done efficiently by iterating the values from end to start, keeping track of a "running" maximum.
• For the greater number of partitions, build on top of the previous results: the current partition may end at serveral possible indices, so assume each of these one by one and maintain the maximum as this partition grows. What follows after the end of the partition can be read from previous results in the table.

I suppose there are several optimisations possible. Like this one:

• It is never needed to have two consecutive partitions that both have more than one member.

  Proof: imagine we have two such consecutive partitions, and the maximum value in the left partition is greater than the maximum value in the right partition. We can shift all values from the left partition into the right partition, except its leftmost value. This will not increase the maximum value in either partition, although it could possibly lower that of the first partition. So we can always replace the original partitioning by one where we don't have two consecutive partitions that both have more than one member.

  A similar reasoning can be used when the maximum value in the left partition is less than or equal to the maximum value in the right partition.

This means we can look at these scenarios:

• Take the leftmost element of the current subarray as a 1-sized partition, and rely on the results for one less partition to see how that plays out for the rest of the subarray.
• Look at other indices where the current partition could end (so it has a greater size than 1), and then select the very next element as a 1-sized partition on its own. We can rely on the results for two partitions less to see what we get for the rest of the subarray.
• Assume that all but the current partition will be size 1 and thus "cramped" at the right side of the subarray. We can then get the results from the one partition less for those remaining partitions.

Here is an implementation:

    public static int solve(int[] values, int numPartitions) {
        int n = values.length;
        int[][] dp = new int[numPartitions+1][n+1];
        // Initialise dp for when there is one partition 
        //    In that case the maximum value in the slice is the outcome
        for (int i = n - 1; i >= 0; i--) {
            dp[1][i] = Math.max(dp[1][i + 1], values[i]); // "running" maximum
        }
        // Initialise dp for when array size is the number of partitions
        for (int p = 1; p <= numPartitions; p++) {
            int i = n - p; // Size of slice is number of partitions
            dp[p][i] = values[i] + dp[p - 1][i + 1];
        }
        // Increment number of partitions: dynamic programming
        for (int p = 2; p <= numPartitions; p++) {
            for (int i = numPartitions - p; i <= n - p; i++) {
                // Split  (i)(i + 1...)...
                int max = values[i]; // Maintain the maximum of the current partition
                int result = max + dp[p - 1][i + 1];
                // Loop to place a singleton (so two splits) somewhere in the slice
                for (int j = i + 2; j <= n - p; j++) {
                    max = Math.max(max, values[j - 1]);
                    if (p > 2) { // Split (i..j-1)(j)(j+1...)...
                        result = Math.min(result, max + values[j] + dp[p - 2][j + 1]);
                    }
                }
                int j = n - p + 1;
                // Split  (i..j-1)(j)(j+1)...(n-1) all cramped to the right
                dp[p][i] = Math.min(result, Math.max(max, values[j - 1]) + dp[p - 1][j]);
            }
        }
        return dp[numPartitions][0];
    }

Tested with these test cases:

    public static void main(String[] args) {
        System.out.printf("%d\n".repeat(7),
            solve(new int[]{1000, 500, 2000, 8000, 1500}, 3), // 9500
            solve(new int[]{3000, 1000, 4000}, 2), // 7000
            solve(new int[]{190, 200, 450, 499, 358, 160}, 3), // 849
            solve(new int[]{10,5,9,3,8,15}, 2), // 25
            solve(new int[]{150, 200, 400, 350, 250}, 3), // 750
            solve(new int[]{78, 45, 12, 56, 85, 45}, 1), // 85
            solve(new int[]{10, 5, 9, 3, 8, 15}, 2) // 25
        );
    }

Output:

9500
7000
849
25
750
85
25

Answered By - trincot