2.1 Most valuable subinterval

We are given an integer array like this:

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

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\le i\le j\le 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$.

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

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.

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

diff file1.txt file2.txt

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

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\le i\le j\le n$, compute the value of the interval $A[i:j]$ and take the maximum.

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))

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\le i\le j\le 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\le j\le 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^{\prime }$, i.e., $\text{val}(A[i^{\prime }:j+1])>\text{val}(A[i:j+1])$. Then wouldn't $A[i^{\prime },j]$ be better for $j$, i.e., wouldn't $T_j$ be $\text{val}(A[i^{\prime },j])$ instead of $\text{val}(A[i,j+1])$? Seems like! Let's calculate it!

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^{\prime }:j]$ is an interval, which is it not if $i^{\prime }=j+1$! We conclude: either $i^{\prime }=j+1$ and the optimal interval for $j+1$ is $A[j+1:j+1]$, meaning $T_{j+1}=0$; or $i^{\prime }\le j$ in which case $i^{\prime }=i$ and $T_{j+1}=T_j+A[j]$. Altogether:

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^{\prime }]$ for some $j^{\prime }\le j$, and then $S_{j+1}=S_j$. Thus

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^{\prime }:i^{\prime }+k]$ have the same value (and both have length $k$) and $i<i^{\prime }$, 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.

6 5 2 -20 9 4 

(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.