Remova as entradas da matriz para classificá-la e maximizar a soma dos elementos

13

Esse desafio é de um teste de admissão a um curso fechado de segurança cibernética. De qualquer forma, isso não tem a ver com segurança cibernética, é apenas para testar as habilidades lógicas e de codificação dos alunos.

Tarefa

Escreva um programa que remova entradas de uma matriz para que os valores restantes sejam classificados em uma ordem estritamente decrescente e sua soma seja maximizada entre todas as outras sequências decrescentes possíveis.

Entrada e saída

A entrada será uma matriz de valores inteiros estritamente maiores que 0e todos diferentes entre si . Você pode escolher entre ler a entrada do arquivo, linha de comando ou stdin.

A saída será uma sub - matriz ordenada por ordem decrescente da entrada, cuja soma é maior que qualquer outra sub-matriz ordenada por ordem descendente.

Nota: [5, 4, 3, 2] é uma sub-matriz de [5, 4, 1, 3, 2], mesmo que 4e 3não seja adjacente. Só porque o 1foi estalado.

Solução Bruteforce

A solução mais simples, é claro, seria iterar entre todas as combinações possíveis da matriz fornecida e procurar uma ordenada com a maior soma, ou seja, em Python :

import itertools

def best_sum_desc_subarray(ary):
    best_sum_so_far = 0
    best_subarray_so_far = []
    for k in range(1, len(ary)):
        for comb in itertools.combinations(ary, k):
            if sum(comb) > best_sum_so_far and all(comb[j] > comb[j+1] for j in range(len(comb)-1)):
                best_subarray_so_far = list(comb)
                best_sum_so_far = sum(comb)
    return best_subarray_so_far

Infelizmente, desde que verificar se a matriz é classificada, e calcular a soma de TI de elementos é e desde que esta operação será feito vezes para partir para , a complexidade de tempo assintótica será

Desafio

Seu objetivo é alcançar uma complexidade de tempo melhor do que a força bruta acima. A solução com a menor complexidade de tempo assintótica é a vencedora do desafio. Se duas soluções tiverem a mesma complexidade de tempo assintótica, o vencedor será aquele com a menor complexidade espacial assintótica.

Nota: Você pode considerar ler, escrever e comparar atômica, mesmo em grandes números.

Nota: Se houver duas ou mais soluções, retorne uma delas.

Casos de teste

Input:  [200, 100, 400]
Output: [400]

Input:  [4, 3, 2, 1, 5]
Output: [4, 3, 2, 1]

Input:  [50, 40, 30, 20, 10]
Output: [50, 40, 30, 20, 10]

Input:  [389, 207, 155, 300, 299, 170, 158, 65]
Output: [389, 300, 299, 170, 158, 65]

Input:  [19, 20, 2, 18, 13, 14, 8, 9, 4, 6, 16, 1, 15, 12, 3, 7, 17, 5, 10, 11]
Output: [20, 18, 16, 15, 12, 7, 5]

Input:  [14, 12, 24, 21, 6, 10, 19, 1, 5, 8, 17, 7, 9, 15, 23, 20, 25, 11, 13, 4, 3, 22, 18, 2, 16]
Output: [24, 21, 19, 17, 15, 13, 4, 3, 2]

Input:  [25, 15, 3, 6, 24, 30, 23, 7, 1, 10, 16, 29, 12, 13, 22, 8, 17, 14, 20, 11, 9, 18, 28, 21, 26, 27, 4, 2, 19, 5]
Output: [25, 24, 23, 22, 17, 14, 11, 9, 4, 2]
array-manipulation subsequence fastest-algorithm Marco
fonte
Relacionado. (Não consigo verificar agora se os dois algoritmos são, de facto equivalentes, mas eu acho que eles poderiam ser.)
Martin Ender
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
Martin Ender

Respostas:

3

Perl

Deve ser O (n ^ 2) no tempo e O (n) no espaço

Atribua números separados por espaço em uma linha a STDIN

#!/usr/bin/perl -a
use strict;
use warnings;

# use Data::Dumper;
use constant {
    INFINITY => 9**9**9,
    DEBUG    => 0,
};

# Recover sequence from the 'how' linked list
sub how {
    my @z;
    for (my $h = shift->{how}; $h; $h = $h->[1]) {
        push @z, $h->[0];
    }
    pop @z;
    return join " ", reverse @z;
}

use constant MINIMUM => {
    how  => [-INFINITY, [INFINITY]],
    sum  => -INFINITY,
    next => undef,
};

# Candidates is a linked list of subsequences under consideration
# A given final element will only appear once in the list of candidates
# in combination with the best sum that can be achieved with that final element
# The list of candidates is reverse sorted by final element
my $candidates = {
    # 'how' will represent the sequence that adds up to the given sum as a
    # reversed lisp style list.
    # so e.g. "1, 5, 8" will be represented as [8, [5, [1, INFINITY]]]
    # So the final element will be at the front of 'how'
    how  => [INFINITY],
    # The highest sum that can be reached with any subsequence with the same
    # final element
    sum  => 0,
    # 'next' points to the next candidate
    next => MINIMUM,   # Dummy terminator to simplify program logic
};

for my $num (@F) {
    # Among the candidates on which an extension with $num is valid
    # find the highest sum
    my $max_sum = MINIMUM;
    my $c = \$candidates;
    while ($num < $$c->{how}[0]) {
        if ($$c->{sum} > $max_sum->{sum}) {
            $max_sum = $$c;
            $c = \$$c->{next};
        } else {
            # Remove pointless candidate
            $$c = $$c->{next};
        }
    }

    my $new_sum = $max_sum->{sum} + $num;
    if ($$c->{how}[0] != $num) {
        # Insert a new candidate with a never before seen end element
        # Due to the unique element rule this branch will always be taken
        $$c = { next => $$c };
    } elsif ($new_sum <= $$c->{sum}) {
        # An already known end element but the sum is no improvement
        next;
    }
    $$c->{sum} = $new_sum;
    $$c->{how} = [$num, $max_sum->{how}];
    # print(Dumper($candidates));
    if (DEBUG) {
        print "Adding $num\n";
        for (my $c = $candidates; $c; $c = $c->{next}) {
            printf "sum(%s) = %s\n", how($c), $c->{sum};
        }
        print "------\n";
    }
}

# Find the sequence with the highest sum among the candidates
my $max_sum = MINIMUM;
for (my $c = $candidates; $c; $c = $c->{next}) {
    $max_sum = $c if $c->{sum} > $max_sum->{sum};
}

# And finally print the result
print how($max_sum), "\n";
Ton Hospel
fonte
3

O(nregistro⁡n)O(n)

{-# LANGUAGE MultiParamTypeClasses #-}

import qualified Data.FingerTree as F

data S = S
  { sSum :: Int
  , sArr :: [Int]
  } deriving (Show)

instance Monoid S where
  mempty = S 0 []
  mappend _ s = s

instance F.Measured S S where
  measure = id

bestSubarrays :: [Int] -> F.FingerTree S S
bestSubarrays [] = F.empty
bestSubarrays (x:xs) = left F.>< sNew F.<| right'
  where
    (left, right) = F.split (\s -> sArr s > [x]) (bestSubarrays xs)
    sLeft = F.measure left
    sNew = S (x + sSum sLeft) (x : sArr sLeft)
    right' = F.dropUntil (\s -> sSum s > sSum sNew) right

bestSubarray :: [Int] -> [Int]
bestSubarray = sArr . F.measure . bestSubarrays

Como funciona

bestSubarrays xsé a sequência de sub-matrizes xsque estão na fronteira eficiente de {maior soma, menor primeiro elemento}, ordenadas da esquerda para a direita, aumentando a soma e aumentando o primeiro elemento.

Para ir de bestSubarrays xspara bestSubarrays (x:xs), nós

  1. divida a sequência em um lado esquerdo com os primeiros elementos menores que xe um lado direito com os primeiros elementos maiores que x,
  2. encontre um novo subarray, acrescentando xo subarray mais à direita no lado esquerdo,
  3. solte o prefixo das sub-matrizes do lado direito com uma soma menor que a nova sub-matriz,
  4. concatenar o lado esquerdo, o novo subarray e o restante do lado direito.

O(registro⁡n)

Anders Kaseorg
fonte
1

Essa resposta se expande na de Ton Hospel.

O problema pode ser resolvido com a programação dinâmica usando a recorrência

T(Eu)=umaEu+max[{0 0}∪{T(j)|0 0≤j<Eu∧umaEu≤umaj}]

(umaEu)T(Eu)EuT

fn solve(arr: &[usize]) -> Vec<usize> {
    let mut tbl = Vec::new();
    // Compute table with maximum sums of any valid sequence ending
    // with a given index i.
    for i in 0..arr.len() {
        let max = (0..i)
            .filter(|&j| arr[j] >= arr[i])
            .map(|j| tbl[j])
            .max()
            .unwrap_or(0);
        tbl.push(max + arr[i]);
    }
    // Reconstruct an optimal sequence.
    let mut sum = tbl.iter().max().unwrap_or(&0).clone();
    let mut limit = 0;
    let mut result = Vec::new();

    for i in (0..arr.len()).rev() {
        if tbl[i] == sum && arr[i] >= limit {
            limit = arr[i];
            sum -= arr[i];
            result.push(arr[i]);
        }
    }
    assert_eq!(sum, 0);
    result.reverse();
    result
}

fn read_input() -> Vec<usize> {
    use std::io::{Read, stdin};
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    s.split(|c: char| !c.is_numeric())
        .filter(|&s| !s.is_empty())
        .map(|s| s.parse().unwrap())
        .collect()
}

fn main() {
    println!("{:?}", solve(&read_input()));
}

Experimente online!

politza
fonte