Input: nums =[1,2,3,12]Output: 6Explanation: The best possible way to form 3 subarrays is:[1],[2], and [3,12] at a total cost of 1+2+3=6.The other possible ways to form 3 subarrays are:-[1],[2,3], and [12] at a total cost of 1+2+12=15.-[1,2],[3], and [12] at a total cost of 1+3+12=16.
Input: nums =[5,4,3]Output: 12Explanation: The best possible way to form 3 subarrays is:[5],[4], and [3] at a total cost of 5+4+3=12.It can be shown that 12is the minimum cost achievable.
Input: nums =[10,3,1,1]Output: 12Explanation: The best possible way to form 3 subarrays is:[10,3],[1], and [1] at a total cost of 10+1+1=12.It can be shown that 12is the minimum cost achievable.
Since the array is small (n <= 50), we can try all possible ways to split the array into 3 contiguous subarrays and compute the sum of their first elements. The minimum sum among all possible splits is the answer.
classSolution {
public:int minimumCost(vector<int>& nums) {
int n = nums.size(), ans = INT_MAX;
for (int i =1; i < n -1; ++i) {
for (int j = i +1; j < n; ++j) {
ans = min(ans, nums[0] + nums[i] + nums[j]);
}
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
funcminimumCost(nums []int) int {
n:= len(nums)
ans:=1<<30fori:=1; i < n-1; i++ {
forj:=i+1; j < n; j++ {
cost:=nums[0] +nums[i] +nums[j]
ifcost < ans {
ans = cost }
}
}
returnans}
1
2
3
4
5
6
7
8
9
10
11
classSolution {
publicintminimumCost(int[] nums) {
int n = nums.length, ans = Integer.MAX_VALUE;
for (int i = 1; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
ans = Math.min(ans, nums[0]+ nums[i]+ nums[j]);
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution {
funminimumCost(nums: IntArray): Int {
val n = nums.size
var ans = Int.MAX_VALUE
for (i in1 until n - 1) {
for (j in i + 1 until n) {
ans = minOf(ans, nums[0] + nums[i] + nums[j])
}
}
return ans
}
}
1
2
3
4
5
6
7
8
classSolution:
defminimumCost(self, nums: list[int]) -> int:
n = len(nums)
ans = float('inf')
for i in range(1, n -1):
for j in range(i +1, n):
ans = min(ans, nums[0] + nums[i] + nums[j])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
impl Solution {
pubfnminimum_cost(nums: Vec<i32>) -> i32 {
let n = nums.len();
letmut ans =i32::MAX;
for i in1..n -1 {
for j in i +1..n {
ans = ans.min(nums[0] + nums[i] + nums[j]);
}
}
ans
}
}