Supprimer les entrées du tableau pour le trier et maximiser la somme des éléments

13

Ce défi passe d'un test d'admission à un cours de cybersécurité à numéro fermé. Quoi qu'il en soit, cela n'a pas à voir avec la cybersécurité, c'est juste pour tester les compétences logiques et de codage des étudiants.

Tâche

Écrivez un programme qui supprime les entrées d'un tableau afin que les valeurs restantes soient triées dans un ordre strictement décroissant et que leur somme soit maximisée parmi toutes les autres séquences décroissantes possibles.

Entrée et sortie

Entrée sera un tableau de valeurs entières strictement supérieur à 0et tous différents les uns des autres . Vous êtes libre de choisir de lire l'entrée du fichier, de la ligne de commande ou de stdin.

La sortie sera un sous - tableau trié par ordre décroissant de celui d'entrée, dont la somme est supérieure à tout autre sous-tableau par ordre décroissant possible.

Note: [5, 4, 3, 2] est un sous - tableau de [5, 4, 1, 3, 2], même si 4et 3ne sont pas adjacents. Tout simplement parce que le a 1été sauté.

Solution Bruteforce

La solution la plus simple serait bien sûr d'itérer parmi toutes les combinaisons possibles du tableau donné et d'en rechercher un trié avec la plus grande somme, c'est-à-dire en 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

Malheureusement, étant donné que la vérification du tri du tableau et le calcul de la somme de ses éléments le sont et que cette opération sera effectuée plusieurs fois pour de à , la complexité temporelle asymptotique sera

Défi

Votre objectif est d'obtenir une meilleure complexité temporelle que la bruteforce ci-dessus. La solution avec la plus petite complexité temporelle asymptotique est la gagnante du défi. Si deux solutions ont la même complexité temporelle asymptotique, le gagnant sera celui avec la plus petite complexité spatiale asymptotique.

Remarque: Vous pouvez envisager de lire, d'écrire et de comparer atomique même sur de grands nombres.

Remarque: S'il existe deux solutions ou plus, renvoyez l'une ou l'autre.

Cas de test

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
la source
En relation. (Je ne peux pas vérifier pour l'instant si les deux algorithmes sont en fait équivalents, mais je pense qu'ils pourraient l'être.)
Martin Ender
Les commentaires ne sont pas pour une discussion approfondie; cette conversation a été déplacée vers le chat .
Martin Ender

Réponses:

3

Perl

Cela devrait être O (n ^ 2) dans le temps et O (n) dans l'espace

Donnez des nombres séparés par un espace sur une ligne à 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
la source
3

O(nJournal⁡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

Comment ça fonctionne

bestSubarrays xs est la séquence de sous-réseaux de xs qui se trouvent à la frontière efficace de {la plus grande somme, le plus petit premier élément}, ordonné de gauche à droite en augmentant la somme et en augmentant le premier élément.

Pour aller de bestSubarrays xsà bestSubarrays (x:xs), nous

  1. diviser la séquence en un côté gauche avec les premiers éléments inférieurs à x, et un côté droit avec les premiers éléments supérieurs àx ,
  2. trouver un nouveau sous-tableau en ajoutant x au le plus à droite sur le côté gauche,
  3. déposez le préfixe des sous-tableaux du côté droit avec une somme plus petite que le nouveau sous-tableau,
  4. concaténer le côté gauche, le nouveau sous-tableau et le reste du côté droit.

Un arbre de doigt prend en charge toutes ces opérations dansO(Journal⁡n) temps.

Anders Kaseorg
la source
1

Cette réponse se développe sur celle de Ton Hospel.

Le problème peut être résolu avec la programmation dynamique en utilisant la récurrence

T(je)=uneje+max[{0}∪{T(j)|0≤j<je∧uneje≤unej}]

où (uneje) est la séquence d'entrée et T(je) la somme maximale réalisable de toute sous-séquence décroissante se terminant par un indice je. La solution réelle peut ensuite être retracée en utilisantT, comme dans le code de rouille suivant.

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()));
}

Essayez-le en ligne!

politza
la source