Geek asks and answers

Pseudocode for an algorithm that finds the following sum?

Given the finite sequence a1, a2, ..., an of integers (which can be negative or positive), its segment is defined as ai, ..... aj for i> = 1 and j <= n. I am trying to create an algorithm that can find the minimum sum of all segments, in other words, for each of the possible segments that can be made from a sequence, summarize their respective terms and make a set consisting of each sum received. To try to make this clearer if sum_a is the sum of segment a1 and sum_b is the sum of a1, a2, etc. For all possible segments, then from all the sums that I get, what would the pseudocode find the minimum sum of all sums of segments?

In particular, how can I find the minimum positive amount?

+3
source share
1 answer

I'm not sure I understood you correctly:

cur_best = +infinity
cur_best_start = 1
cur_best_end = n
for start = 1..n:
    for end = start..n:
        sum_subsequence = 0
        for i = start..end:
            sum_subsequence = sum_subsequence + a_i
        if (sum_subsequence > 0) and (sum_subsequence < cur_best):
            cur_best = sum_subsequence
            cur_best_start = start
            cur_best_end = end

Minimum of all subsequences apositive.

+4
source

More articles:


All Articles