FastPrepFastPrep
Problem Brief

Efficient Trek

INTERNOA

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

Example: There are n = 6 trails with lengths trails= [10, 5, 9, 3, 8, 15] and record = 2. One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 + 15 = 25. Return 25.

Function Description

Complete the function efficientTrek in the editor.

efficientTrek has the following parameters:

  1. int trails[]: an array of integers denoting the order and length of the trails.
  2. int record: the number of days to cover all the trails.

Returns

int: the minimum sum of the longest trails on each day

1Example 1

Input
trails = [10, 5, 9, 3, 8, 15], record = 2
Output
25
Explanation
One optimal solution is for the hiker to cover the first trail on the first day, and the remaining trails on the second day. On the first day, the longest trail is 10, and on the second day, it is max(5, 9, 3, 8, 15) = 15. The sum of the lengths of the longest trails is 10 + 15 = 25. Return 25.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 300
  • 1 ≤ record ≤ n ≤ 300
  • 1 ≤ trails[i] ≤ 10^5
public int efficientTrek(int[] trails, int record) {
  // write your code here
}
Input

trails

[10, 5, 9, 3, 8, 15]

record

2

Output

25

Sign in to submit your solution.