I'm having trouble understanding what constitutes a "minimal sum section" of an integer array. My book defines it as the following:

Let $a[0],\dots, a[n-1]$ be the integer values of an array $a$.
A section of $a$ is a continuous piece $a[i],\dots,a[j]$, where $0\le i \le j < n$. We write $S_i,_j$ for the sum of that section: $a[i] + a[i+1]+\dots+a[j]$.
A minimal-sum section is a section $a[i],\dots,a[j]$ of $a$ such that the sum $S_{i,j}$ is less than or equal to the sum $S_{i',j'}$ of any other section $a[i'],\dots,a[j']$ of $a$.

My confusion comes with one of the examples that follow this definition:

The array [1,-1,3,-1,1] has two minimal-sum sections [1,-1] and [-1,1] with minimal sum 0.

But, wouldn't the minimal sum section be $[-1]$ ?

In a later example they give:

array $[-1,3,-2]$

Minimal sum

section $[-2]$

So, in the last example they definitely counted one element as the minimal sum section, but not in the first one. Any clarification on why this is so would be greatly appreciated.

  • 2
    $\begingroup$ If your book is Huth, M; Ryan, M: "Logic in Computer Science: Modelling and Reasoning about Systems" (part in question 4.3.3 A case study: minimal-sum section), I take it to be a simple error on behalf of the authors and lectors in an example intended to show something else: that minimal-sum sections do not need to be unique. (9780521543101, no errata found at Cambridge University Press.) $\endgroup$ – greybeard Nov 11 '19 at 6:52
  • 1
    $\begingroup$ Looks like a mistake. According to the definition, the minimal sum section in your first example should indeed be $-1$. $\endgroup$ – Yuval Filmus Nov 11 '19 at 9:54
  • $\begingroup$ @greybeard yes that's the book. $\endgroup$ – Papaya Automata Nov 11 '19 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.