Дан массив целых чисел nums. Нужно разбить его на три непрерывные непустые части. Верните минимально возможную сумму первых элементов каждой из частей после такого разбиения. Гарантируется, что разбиение всегда возможно.
Пример 1:
Ввод: nums = [3,1,2,4,5] Вывод: 6 Объяснение: [3],[1],[2,4,5] → 3 + 1 + 2 = 6
Пример 2:
Ввод: nums = [5,2,1,3] Вывод: 8 Объяснение: [5],[2],[1, 3] → 5 + 2 + 1 = 8
Ограничения:
len(nums) ≥ 3public class Solution {
public static int MinSplitCost(List<int> nums) {
int min1 = int.MaxValue, min2 = int.MaxValue;
for (int i = 1; i < nums.Count; i++) {
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
}
return nums[0] + min1 + min2;
}
}#include <vector>
#include <climits>
using namespace std;
int minSplitCost(vector<int>& nums) {
int min1 = INT_MAX, min2 = INT_MAX;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
}
return nums[0] + min1 + min2;
}package main
func minSplitCost(nums []int) int {
min1, min2 := int(1e9), int(1e9)
for i := 1; i < len(nums); i++ {
if nums[i] < min1 {
min2 = min1
min1 = nums[i]
} else if nums[i] < min2 {
min2 = nums[i]
}
}
return nums[0] + min1 + min2
}import java.util.*;
public class Solution {
public int minSplitCost(List<Integer> nums) {
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
for (int i = 1; i < nums.size(); i++) {
if (nums.get(i) < min1) {
min2 = min1;
min1 = nums.get(i);
} else if (nums.get(i) < min2) {
min2 = nums.get(i);
}
}
return nums.get(0) + min1 + min2;
}
}from typing import *
def min_split_cost(nums: List[int]) -> int:
min1, min2 = float('inf'), float('inf')
for i in range(1, len(nums)):
if nums[i] < min1:
min1, min2 = nums[i], min1
elif nums[i] < min2:
min2 = nums[i]
return nums[0] + min1 + min2/**
* @param {number[]} nums
* @return {number}
*/
export function minSplitCost(nums) {
let min1 = Number.MAX_SAFE_INTEGER;
let min2 = Number.MAX_SAFE_INTEGER;
for (let i = 1; i < nums.length; i++) {
if (nums[i] < min1) {
min2 = min1;
min1 = nums[i];
} else if (nums[i] < min2) {
min2 = nums[i];
}
}
return nums[0] + min1 + min2;
}Оценка сложности
O(n), где n — размер numsO(1)