▲

3

▼

🚀 Однопроходный жадный скан для задачи максимизации функционала на триплетах

leetcoder, 02-04-2025 , 30

Условие задачи — 2874. Maximum Value of an Ordered Triplet II.

📄 Описание задачи

Дан массив целых чисел nums (индексация с нуля).
Нужно найти максимум выражения (nums[i]-nums[j])·nums[k] среди всех троек индексов i < j < k.
Если все такие значения отрицательны, вернуть 0.

💡 Идея

Выражение (nums[i]-nums[j])·nums[k] будет наибольшим, при фиксированном k, если:

• Число nums[i] наибольшее
• Разность nums[i]-nums[j] максимальна

Значит, на каждом шаге мы можем поддерживать максимальное значение разности (nums[i]-nums[j]) до текущего индекса и умножать его на nums[k], обновляя лучший результат.

🔍 Детали подхода

1. Идем по массиву слева направо. На каждом шаге:
   • max_val хранит максимум из всех предыдущих чисел (nums[..i]);
   • max_diff — максимум nums[i]-nums[j] на текущий момент;
   • умножаем max_diff на текущий nums[k] и обновляем best.
2. Всё делается за один проход, без дополнительных структур данных.

⏱️ Асимптотика

• Время: O(n) — один проход по массиву
• Память: O(1) — используются только 3 переменные

🧾 Исходный код

impl Solution {
    pub fn maximum_triplet_value(nums: Vec<i32>) -> i64 {
        nums.into_iter().fold((0i64, 0, 0), |(best, max_diff, max_val), x| (
            best.max(x as i64 * max_diff as i64),
            max_diff.max(max_val - x),
            max_val.max(x),
        )).0
    }
}

Tags: #rust #algorithms #greedy