Решение задачи №138 от UniLecs (Максимальная последовательность по модулю)

main.rs

extern crate itertools;

use itertools::{Itertools, Either::*};

// Самый первый вариант — разбиваем массив
// на вектор отрицательных чисел и вектор положительных,
// а затем возвращаем тот, для которого абсолютная сумма элементов больше.
fn max_abs_sum_subset_1(arr: &[i32]) -> Vec<i32> {
    let (neg, pos): (Vec<_>, Vec<_>) = arr.iter().cloned()
        .partition_map(|x| if x < 0 { Left(x) } else { Right(x) });
        
    let abs_sum = |arr: &[_]| arr.iter().sum::<i32>().abs();
    
    if abs_sum(&neg) > abs_sum(&pos) { neg } else { pos }
}

// Можно сделать и лучше, считая суммы при первом проходе по массиву.

// Для использования partition_map используемый для сбора тип должен
// реализовывать типажи Default (определено значение по умолчанию)
// и Extend (расширяется элементами из итератора).
#[derive(Default)]
struct SumSubset {
    sum: i32, // Сумма элементов
    set: Vec<i32>, // Сами элементы
}

impl Extend<i32> for SumSubset {
    fn extend<I: IntoIterator<Item = i32>>(&mut self, vals: I) {
        let vals = vals.into_iter();
        let (lo, hi) = vals.size_hint();
        self.set.reserve(hi.unwrap_or(lo));
        
        for x in vals {
            self.sum += x;
            self.set.push(x);
        }
    }
}

// Разбиваем массив на вектор отрицательных и вектор положительных,
// попутно считая суммы, и возвращаем тот, у которого по модулю сумма больше.
fn max_abs_sum_subset_2(arr: &[i32]) -> Vec<i32> {
    let (neg, pos): (SumSubset, SumSubset) = arr.iter().cloned()
        .partition_map(|x| if x < 0 { Left(x) } else { Right(x) });
        
    if neg.sum.abs() > pos.sum { neg.set } else { pos.set }
}

// Как и в первом случае, мы создаём два вектора (=две аллокации в куче),
// один из которых обязательно уничтожается при выходе из функции.
// Мы можем сократить потребление памяти, сначала подсчитав суммы
// и лишь потом вернув нужные элементы на основании того, какая сумма больше.

fn max_abs_sum_subset_3(arr: &[i32]) -> Vec<i32> {
    let (mut neg_sum, mut pos_sum) = (0i32, 0i32);
    
    arr.iter().for_each(|&x| if x < 0 { neg_sum -= x} else { pos_sum += x });
    
    if neg_sum > pos_sum {
        arr.iter().cloned().filter(|&x| x < 0).collect()
    } else {
        arr.iter().cloned().filter(|&x| x > 0).collect()
    }
}

fn main() {
    // Все три способа эквивалентны и потому дают один и тот же результат

    let arr = &[-1, 2, -1, 3, -4]; //Ответ: [-1, -1, -4]
    println!("{:?}", max_abs_sum_subset_1(arr));
    println!("{:?}", max_abs_sum_subset_2(arr));
    println!("{:?}", max_abs_sum_subset_3(arr));
    
    let arr = &[-1, 2, -3, 2, -2, 8]; //Ответ: [2, 2, 8]
    println!("{:?}", max_abs_sum_subset_1(arr));
    println!("{:?}", max_abs_sum_subset_2(arr));
    println!("{:?}", max_abs_sum_subset_3(arr));
}

Возьмём произвольное подмножество элементов исходного массива.

Допустим, сумма его элементов положительна. Тогда:

1. Если это подмножество содержит отрицательные элементы, то его сумму можно увеличить, исключив отрицательные элементы;
2. Если это подмножество содержит не все положительные элементы из исходного массива, то, добавив эти элементы, сумму подмножества можно также увеличить.

Пусть теперь сумма элементов подмножества отрицательна. Тогда аналогично:

1. Если это подмножество содержит положительные элементы, то его сумму по модулю можно увеличить, исключив эти элементы;
2. Если это подмножество содержит не все отрицательные элементы исходного массива, то сумму по модулю этого множества можно увеличить, добавив эти элементы.

Условимся приписывать подмножествам с нулевой суммой определённый знак суммы (какой конкретно — не важно). Тогда получаем, что любое подмножество можно преобразовать, увеличив по модулю сумму его элементов. Есть только два исключения: подмножество из всех положительных элементов массива и всех отрицательных элементов. Т. о., для нахождения ответа на вопрос задачи требуется подсчитать суммы элементов этих двух подмножеств и на основании их отношения по модулю выбрать нужное.