Сложность: medium
Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.
Пример:
Input: nums = [1,5,11,5]
Output: true
👨💻 Алгоритм:
1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false.
2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов.
3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве.
😎 Решение:
func canPartition(_ nums: [Int]) -> Bool {
let sum = nums.reduce(0, +)
if sum % 2 != 0 { return false }
let target = sum / 2
var dp = [Bool](repeating: false, count: target + 1)
dp[0] = true
for num in nums {
for j in stride(from: target, through: num, by: -1) {
dp[j] = dp[j] || dp[j - num]
}
}
return dp[target]
}Ставь 👍 и забирай 📚 Базу знаний