Låt A vara en sekvens av n ≥ 0 reella tal. En följd av A är en sekvens av sammanhängande element i A. En maximal poäng subsekvens av A är en subsekvens med största summan av dess element, som kan hittas i O (n) tid av Kadane dynamiska programmeringsalgoritm. Vi anser i det här dokumentet att två problem med maximal poängsättning undersekvenser av en sekvens. Båda dessa problem uppstår i samband med buffertminnesminimering i datornätverk. Den första, som kallas INSERTION I EN SEQUENCE MED SCORES (ISS), består i att infoga ett givet reellt tal x i A på ett sådant sätt att minimera summan av en maximal poäng följd av den resulterande sekvensen, som enkelt kan göras i O(n 2 ) tid genom att successivt tillämpa Kadane algoritm för att beräkna den maximala scoring subsekvensen av den resulterande sekvensen som motsvarar varje möjlig insättningsposition för x. Vi visar i denna artikel att ISS-problemet kan lösas i linjär tid och rum med en mer specialiserad algoritm. Det andra problemet vi anser i denna rapport är SORTING A SEQUENCE AV SCORES (SSS) ett, anges enligt följande: hitta en permutation A ′ av A som minimerar summan av en maximal poäng subsekvens. Vi visar att SSS problemet är starkt NP-Hard och ger en 2- approximation algoritm för det.
Exakt, i en första papper som vi ansåg problemet med, med tanke på en sekvens A av n reella tal och ett reellt antal x, hitta ett index p... {0,..., n} som minimerar MS(A (x→p) ), och vi visade att detta kan göras med hjälp av en enkel linjär tid algoritm REF.
Insertion and Sorting in a Sequence of Numbers Minimizing the Maximum Sum of a Contiguous Subsequence
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}