Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 6 / c

Table of contents
- Solution c

Solution

This version of Kadane's algorithm, named for Joseph Born Kadane, permits the empty subsequence. For

j \geq 1

, let

E_{j}

be the maximum of zero and the weight of a contiguous subsequence ending exactly at position

j

. Let

B_{j}

be the best weight anywhere in the first

j

E_{0} = B_{0} = 0, E_{j} = max (0, E_{j - 1} + a_{j}), B_{j} = max (B_{j - 1}, E_{j}) .

A segment ending at

j

either extends one ending at

j - 1

or starts at

j

; the zero candidate permits discarding a negative predecessor and the empty answer. Any best segment of the first

j

positions either ends at

j

or already occurs in the first

j - 1

. These two decompositions prove the dynamic programming equations by induction.

Here is an implementation returning endpoints, using zero-based indexing:

best_segment(a):
    end_weight = best_weight = 0
    start = best_lo = best_hi = 0
    for j in range(len(a)):
        trial = end_weight + a[j]
        if trial <= 0:
            end_weight = 0
            start = j+1
        else:
            end_weight = trial
        if end_weight > best_weight:
            best_weight = end_weight
            best_lo, best_hi = start, j+1
    return (best_lo, best_hi, best_weight)

There is exactly one addition per input element, hence

n

O (n)

comparisons. Auxiliary storage is

O (1)

. The all-negative case retains interval

[0, 0)

and weight zero. The example returns

[3, 6)

and weight 8, hence the desired contiguous subsequence.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version