Entfernen Sie Einträge aus dem Array, um es zu sortieren und die Summe der Elemente zu maximieren

13

Diese Herausforderung reicht von einem Zulassungstest bis zu einem Cyber-Sicherheitskurs mit geschlossenen Nummern. Wie auch immer, es hat nichts mit Cybersicherheit zu tun, sondern dient nur dazu, die logischen Fähigkeiten und die Codierungsfähigkeiten der Schüler zu testen.

Aufgabe

Schreiben Sie ein Programm, das Einträge aus einem Array entfernt, sodass die verbleibenden Werte in einer streng absteigenden Reihenfolge sortiert werden und ihre Summe die unter allen anderen möglichen absteigenden Folgen maximierte ist.

Ein- und Ausgang

Eingang wird ein Array von ganzzahligen Werten sein streng größer als 0und alle voneinander verschieden . Sie können frei wählen, ob Sie Eingaben aus einer Datei, einer Befehlszeile oder stdin lesen möchten.

Die Ausgabe ist eine absteigend sortierte Unteranordnung der Eingabe, deren Summe größer ist als jede andere mögliche absteigend sortierte Unteranordnung.

Hinweis: [5, 4, 3, 2] ist ein Subarray von [5, 4, 1, 3, 2], auch wenn 4und 3nicht benachbart sind. Nur weil das 1geknallt war.

Bruteforce-Lösung

Die einfachste Lösung wäre natürlich, unter allen möglichen Kombinationen des gegebenen Arrays zu iterieren und nach einem sortierten mit der größten Summe zu suchen, das wäre in 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

Leider ist die Komplexität der asymptotischen Zeit , da überprüft wird, ob das Array sortiert ist und die Summe seiner Elemente berechnet wird, und da diese Operation Zeiten für von bis durchgeführt wird

Herausforderung

Ihr Ziel ist es, eine bessere Zeitkomplexität als die oben genannte Bruteforce zu erreichen. Die Lösung mit der geringsten asymptotischen Zeitkomplexität ist der Gewinner der Herausforderung. Wenn zwei Lösungen dieselbe asymptotische zeitliche Komplexität aufweisen, ist der Gewinner diejenige mit der geringsten asymptotischen räumlichen Komplexität.

Hinweis: Sie betrachten können , das Lesen, Schreiben und Vergleichen Atom auch auf große Zahlen.

Hinweis: Wenn zwei oder mehr Lösungen vorhanden sind, geben Sie eine davon zurück.

Testfälle

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
quelle
Verbunden. (Ich kann momentan nicht überprüfen, ob die beiden Algorithmen tatsächlich gleichwertig sind, aber ich denke, dass dies der Fall sein könnte.)
Martin Ender,
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Martin Ender

Antworten:

3

Perl

Dies sollte O (n ^ 2) in der Zeit und O (n) im Raum sein

Geben Sie STDIN durch Leerzeichen getrennte Zahlen in einer Zeile

#!/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";
Tonne Hospel
quelle
3

Ö(nLog⁡n)Ö(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

Wie es funktioniert

bestSubarrays xsist die Folge von Subarrays xsan der effizienten Grenze von {größte Summe, kleinstes erstes Element}, geordnet von links nach rechts durch Erhöhen der Summe und Erhöhen des ersten Elements.

Um von bestSubarrays xszu gehen bestSubarrays (x:xs), wir

  1. Teilen Sie die Sequenz in eine linke Seite mit ersten Elementen kleiner als xund eine rechte Seite mit ersten Elementen größer als auf x.
  2. Suchen Sie ein neues Subarray, indem Sie xdem Subarray ganz rechts auf der linken Seite voranstellen.
  3. Löschen Sie das Präfix von Subarrays von der rechten Seite mit einer kleineren Summe als das neue Subarray.
  4. Verketten Sie die linke Seite, das neue Subarray und den Rest der rechten Seite.

Ö(Log⁡n)

Anders Kaseorg
quelle
1

Diese Antwort erweitert die Antwort von Ton Hospel.

Das Problem kann mit der dynamischen Programmierung unter Verwendung der Rekursion gelöst werden

T(ich)=einich+max[{0}∪{T(j)|0≤j<ich∧einich≤einj}]

(einich)T(ich)ichT

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

Probieren Sie es online!

Politza
quelle