| dbo:abstract
|
- Στην πληροφορική, το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: maximum sum subarray problem) είναι ένα πρόβλημα όπου έχουμε μια σειρά (πίνακα) από αριθμούς (θετικούς, αρνητικούς ή μηδενικούς) και ψάχνουμε τη συνεχή υποσειρά (υποπίνακα) αριθμών που δίνει το μεγαλύτερο άθροισμα. Για παράδειγμα, στη σειρά των αριθμών −2, 1, −3, 4, −1, 2, 1, −5, 4 η υποσειρά αριθμών με το μέγιστο άθροισμα είναι η 4, −1, 2, 1, με άθροισμα 6. (el)
- In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. Formally, the task is to find indices and with , such that the sum is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero. For example, for the array of values [−2, 1, −3, 4, −1, 2, 1, −5, 4], the contiguous subarray with the largest sum is [4, −1, 2, 1], with sum 6. Some properties of this problem are: 1.
* If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array. 2.
* If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array (or the empty subarray, if it is permitted). 3.
* Several different sub-arrays may have the same maximum sum. This problem can be solved using several different algorithmic techniques, including brute force, divide and conquer, dynamic programming, and reduction to shortest paths. (en)
- Em Ciência da Computação, encontrar a sublista contígua de maior soma a partir de uma lista de números é um problema bastante conhecido. Na seqüência acima, a sublista contígua de maior soma é [20, 50, -1, 3] e a soma total desse trecho é 72. Tipicamente, a lista de números a ser computada como entrada deve ter números positivos e negativos. Dessa forma, ao encontrar um número negativo vizinho a uma sublista de maior soma computada até então, uma das dificuldades do problema no decorrer da sua resolução é avaliar se esse número negativo deve ser acrescido à sublista ou não. Essa avaliação é necessária porque depois de um número negativo poderão vir na seqüência um ou mais números positivos que compensem o decréscimo resultante da inclusão daquele número negativo. Por outro lado, esse mesmo número negativo vizinho poderá não ser incorporado à sublista de maior soma, pois o resultado final seria uma soma menor do que a obtida até então. Para uma lista que contenha apenas números positivos, o resultado de maior soma será simplesmente a lista inteira dada como entrada. Nos algoritmos que serão apresentados a seguir, quando uma lista de números negativos é dada como entrada ou ainda se uma sublista parcial computada ao longo da resolução do problema resultar numa soma negativa, o resultado deverá ser zero, ou seja, o equivalente a obter como resposta uma lista vazia. (pt)
- 在计算机科学中，最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4，其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。 该问题最初由布朗大学的教授于1977年提出，当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的提出了该问题的线性算法。（）。 (zh)
|
| rdfs:comment
|
- Στην πληροφορική, το πρόβλημα μέγιστου αθροίσματος υποακολουθίας (Αγγλικά: maximum sum subarray problem) είναι ένα πρόβλημα όπου έχουμε μια σειρά (πίνακα) από αριθμούς (θετικούς, αρνητικούς ή μηδενικούς) και ψάχνουμε τη συνεχή υποσειρά (υποπίνακα) αριθμών που δίνει το μεγαλύτερο άθροισμα. Για παράδειγμα, στη σειρά των αριθμών −2, 1, −3, 4, −1, 2, 1, −5, 4 η υποσειρά αριθμών με το μέγιστο άθροισμα είναι η 4, −1, 2, 1, με άθροισμα 6. (el)
- 在计算机科学中，最大子数列问题的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4，其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。 该问题最初由布朗大学的教授于1977年提出，当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的提出了该问题的线性算法。（）。 (zh)
- In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. Formally, the task is to find indices and with , such that the sum is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero. Some properties of this problem are: (en)
- Em Ciência da Computação, encontrar a sublista contígua de maior soma a partir de uma lista de números é um problema bastante conhecido. Na seqüência acima, a sublista contígua de maior soma é [20, 50, -1, 3] e a soma total desse trecho é 72. Para uma lista que contenha apenas números positivos, o resultado de maior soma será simplesmente a lista inteira dada como entrada. (pt)
|
