\( \newcommand{\Z}{\mathbb{Z}} \newcommand{\val}{\textnormal{val}} \)

We are given an integer array like this:

A = [-8, 5, -4, 7, -9, 3, 0, 7, -5, 8, -1, 2, -5, 2, 9, -3]

and are interested in subintervals. For example, in python notation,

A[3:7] = [7, -9, 3, 0]

is a subinterval of $A$. In general, $A[i:j]$ is the interval starting at index $i$ and ending at (and including) index $j$. Thus $A[i:j]$ has length $j-i$ and $A[i:i]$ is the empty array. The notation $A[i:j]$ makes sense if and only if $0 \leq i \leq j \leq n$ (although python is more liberal here and things like $A[1:-1]$ are defined but mean something else).

The value of an interval is the sum of its entries. So $A[3:7]$ has value $7 - 9 + 3 + 0 = 1$.

Problem Given an array of integers as in the example above, compute the maximum value of a subinterval (this includes the possibility of the empty subinterval, so the maximum value is always at least 0).

Input: A single line containing $n \geq 0$ integers, separated by spaces. These are the elements of the input array.

Output: A single line containing a single integer, the maximum value of a subinterval.

Sample input: 

-8 5 -4 7 -9 3 0 7 -5 8 -1 2 -5 2 9 -3

Sample output: 

20

Test cases

Before starting to code, you should think of a handful of test cases (unless this is during an actual competition). Write them into a file and use them to test your algorithm later on.

Exercise Write test cases for this problem. In particular,

  1. the above example;
  2. another hand-crafted example;
  3. edge cases: an array with only positive numbers; an array with only negative numbers; an empty array; other edge cases you can come up with.

Create a sub-directory testcases. For each test case compute the answer by hand and write it into a file. Produce a pair file like all-negative.in and all-negative.out.

Exercise Write a program that generates random instances. Here is mine in action:

python generate-random-test-cases.py 10 -20 20                                    
-9 18 19 -14 2 -10 12 -16 14 18

From here, we will proceed as follows: we will first write a pretty simple but inefficient solution (in fact, of running time $O(n^3)$). Being simple, it is easier to make it correct. We will then test our inefficient solution against our testcases. This is easy if you have a unix shell like bash etc.: 

python cubic-but-wrong.py < testcases/example-in-lecture-notes.in
20

Using the command line program diff, we can compare it to the (hopefully) correct output, stored in example-in-lecture-notes.out: 

python cubic-but-wrong.py < testcases/example-in-lecture-notes.in | diff -b - testcases/example-in-lecture-notes.out                        

python cubic-but-wrong.py < testcases/all-positive.in  | diff -b - testcases/all-positive.out
1c1
< 4
---
> 5
How to use diff: The command diff compares two files. If the files are identical, its output is empty. Otherwise it tells you which lines have differences and at which position (it's a bit more complicated than that). The option -b tells diff to ignore changes of whitespace amount. For example, it would treat TU Chemnitz and TU Chemnitz as identical but as different from TUChemnitz. So usually you use diff with two files as input arguments: 
diff file1.txt file2.txt

Here, one input to be compared is the output of our program. We could of course store it in some temporary file and then compare it: 

python cubic-but-wrong.py < testcases/example-in-lecture-notes.in >. temp.out                            
diff -b temp.out

I wrote cubic-but-wrong.py to read from stdin (the console user input). So instead of manually

We see that our wrong implementation succeeds on the sample input -8 5 -4 7 -9 3 0 7 -5 8 -1 2 -5 2 9 -3 that we have seen above but fails on all-positive.in, which is 1 1 1 1 1. The command diff shows us the difference: its first input (stdin as specified by -) has 4, but the second input, testcases/all-positive.out, has a 5.

The trivial solution

The trivial solution is the iterate over all pairs $(i,j)$ with $0 \leq i \leq j \leq n$, compute the value of the interval $A[i:j]$ and take the maximum.

Exercise What is the running time of the algorithm just described?

Here is my implementation of the trivial algorithm, which you can also find in cubic-but-wrong.py. 

def maximum_sum(array):
    n = len(array)
    max_so_far = 0
    for i in range(0,n):
        for j in range(i+1,n):
            array_here = array[i:j]
            sum_here = sum(array[i:j])
            # print("array[", i, ":", j, "] = ", array_here, ", sum is ", sum_here)
            max_so_far = max(max_so_far, sum(array[i:j]))
    return max_so_far

array = list(map(int, input().split()))
print(maximum_sum(array))

Exercise Find the bug in my code, correct it, and test it.

Pitfalls

When working with arrays, an eternal pitfall is indexing and one-off-errors: do we include the right boundary or don't we? In python, array[i:j] includes index $i$ but not index $j$. Weirdly, randint(i,j) would include both $i$ and $j$. In my implementation, line 5, for j in range(i+1,n+1): might raise eyebrows. Indeed, we could start at $i$ instead of $i+1$, but then array[i:i] would be the empty array, having value $0$, and we have initialized our max_so_far to $0$. More important is the $n+1$ in range(i+1,n+1): we want all pairs $(i,j)$ with $0 \leq i \leq j \leq n$, so in particular we want $j=n$ so the array array[i:n] ends at the right-most index, $n-1$. To make the range include $n$, we have to let it run to $n+1$.

The linear algorithm: Dynamic Programming

As usual in dynamic programming, we have to think about what partial results we want to compute and store. For an index $0 \leq j \leq n$, we will compute two things:

  1. $S_j$, the value of the best subinterval of $A[0:j]$.
  2. $T_j$, the value of the best subinterval of the form $A[i:j]$

Savor the difference: for $j=8$, the interval $A[2:6]$ would qualify for Point 1, as $A[2:6]$ is a subinterval of $A[0:j]$. However, it does not qualify for Point 2, since it is not of the form $A[i:8]$.

Initialization. For $j=0$, we have $A[0:0] = []$. This has only one subinterval (itself), which has value $0$, and therefore $S_j = 0$. The subinterval $A[0:0]$ is also of the form $A[i:j]$ since $j=0$, and thus $T_j = 0$, as well.

Update. Suppose we have computed $S_{j}$ and $T_{j}$. We describe now how to compute $T_{j+1}$. Let $i$ be such that $A[i:j]$ has maximum value among all intervals with right boundary $j$, i.e., has value $T_{j}$. What about $A[i:j+1]$? Is it an optimal interval with right-boundary $j+1$? Well, suppose there was a better $i'$, i.e., $\val(A[i':j+1]) \gt \val(A[i:j+1])$. Then wouldn't $A[i',j]$ be better for $j$, i.e., wouldn't $T_{j}$ be $\val(A[i',j])$ instead of $\val(A[i,j+1])$? Seems like! Let's calculate it!

\begin{align*} \val(A[i':j+1]) & \gt \val(A[i:j+1]) \tag{by assumption} \\ \val(A[i':j]) + A[j] & \gt \val(A[i:j]) + A[j] \tag{by what $\val$ is}\\ \val(A[i':j]) & \gt \val(A[i:j]) \\ \end{align*}

The last line is a contradiction because we assumed $A[i:j]$ was optimal among intervals of the form $A[?:j]$. This reasoning is of course only sound if $A[i':j]$ is an interval, which is it not if $i' = j+1$! We conclude: either $i'=j+1$ and the optimal interval for $j+1$ is $A[j+1:j+1]$, meaning $T_{j+1} = 0$; or $i' \le j$ in which case $i' = i$ and $T_{j+1} = T_{j} + A[j]$. Altogether:

\begin{align} T_{j+1} = \max(0, T_{j} + A[j]) \ . \label{update-T-j} \end{align}

The update rule for $S_j$ is simple. If the best subinterval of $A[0:j+1]$ has the form $A[i:j+1]$, then it qualifies for Point 2 and $S_{j+1} = T_{j+1}$; or it's not, then it is $A[i:j']$ for some $j' \leq j$, and then $S_{j+1} = S_{j}$. Thus

\begin{align*} S_{j+1} = \max(T_{j+1}, S_{j}) \ . \end{align*}

Problem Implement the linear time dynamic programming algorithm just described.

More Information

We don't only want to compute the value of the best subinterval. We want to know the best subinterval itself. So our algorithm should output three things: left, right, and value. Since ICPC-style problems are mostly judged by running them on test inputs and comparing the output to the correct test outputs, we run into difficulties if answers are not unique. Thus, we introduce the following tie breaking rules:

  1. If two intervals have the same value, the smaller (shorter) interval wins.
  2. If two intervals have the same value and the same length, then the one more to the left wins. That is, if $A[i:i+k]$ and $A[i':i'+k]$ have the same value (and both have length $k$) and $i \lt i'$, then $A[i:i+k]$ wins, i.e., is considered better.

Under these tie-breaking rules, every array has a unique optimal interval $A[i:j]$. In particular if all entries are negative, then $i=j=0$ is the optimal solution.

Problem Adapt the cubic and the linear algorithm such that they output three integers $i j v$, separated by a single space, such that $A[i:j]$ is the optimal subinterval and $v$ is its value.

Sample input: 

6 5 2 -20 9 4

Sample output: 

(4, 6, 13)

More test cases

most-valuable-interval-testcases.zip

I didn't provide correct answers for those test cases. You can check the smaller ones against the cubic algorithm, which is hopefully correct.