# Output intervals for the optimal subarrays

Consider an array A of integers of length n. The k-max subarray sum asks us to find up to $$\k \leq 3\$$ (contiguous) non overlapping subarrays of A with maximum sum. If A is all negative then this sum will be 0. If A = [-1, 2, -1, 2, -1, 2, 2] and k=2 for example, then the two subarrays could be [2, -1, 2] and [2, 2] with total sum 7.

Output a list of index pairs representing the subarrays that are being used to form the final k-max subarray sum. In the example just shown I would like the output to be [(1, 3), (5, 6]] to show the subarrays as index pairs in the original array.

# Examples:

[8, -5, 1, 0, -6, -7, 2, 4, 0, -1, -1, 6, -2, 5, 7, 8]

k = 1 should give [(6, 15)].
k = 2 should give [(0,0), (6, 15)].
k = 3 should give [(0,0), (6,7), (11, 15)]

[-3, 0, 2, 2, 0, 0, -1, 1, 3, -2]

k = 1 should give [(1, 8)]
k = 2 should give [(1, 3), (7, 8)]
k = 3 should give [(1, 3), (7, 8)]

[2,  5, -5,  5,  2, -6,  3, -4,  3, -3, -1,  1,  5, -2,  2, -5]

k = 1 should give [(0, 4)]
k = 2 should give [(0, 4), (11, 12)]
k = 3 should give [(0, 1), (3, 4), (11, 12)]

[2, -12,  -3,   5, -14,  -4,  13,   3,  13,  -6, -10,  -7,  -2, -1,   0,  -2,  10,  -9,  -4,  15]

k = 1 should give [(6, 8]]
k = 2 should give [(6, 8), (19, 19)]
k = 3 should give [(6, 8), (16, 16), (19, 19)]

[1, 1, -1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1]

k = 1 should give [(8, 16)]
k = 2 should give [(0, 1), (8, 16)]
k = 3 should give [(0, 1), (3, 3), (8, 16)]


You can 1-index if you prefer. You may also output a flat list of indices rather than a list of pairs.

# Input

An array of integers and a positive integer k.

k will be at most 3.

# Restriction

Your code should run in linear time. That is, its running time must be $$\O(n)\$$.

• You should put $k\leq3$ in bold, and probably also a bit higher, as it's quite significant. Feb 2 at 15:09
• @CommandMaster Thank you.
– Simd
Feb 2 at 15:11
• Are we allowed to use other types of indices for the output? For example, is 1-indexed okay? Is non-inclusive okay? Is half-inclusive okay? Feb 2 at 16:08
• @CursorCoercer you can 1 index but other than that please stay with the way I have done it.
– Simd
Feb 2 at 16:11
• Shouldn't the first example have for k=2 the subarray containing 1?
– qwr
Feb 6 at 19:26

# Python 3, 484 bytes

def m(r,x):
b=c=t=0;s=(0,0)
for f in range(len(r)):
c+=r[f]
if c>t:t=c;s=(b+x,f+x+1)
if c<=0:b=f+1;c=0
return s,t
def f(r,k):
p=[]
for j in range(k):
n=x=(0,0);i=a=0;g=[*zip([*zip(x,*p)][1],[*zip(*p,(len(r),))][0])]
for s in p:
z,t=m([-a for a in r[s[0]:s[1]]],s[0])
if i<t:i=t;n=z;h=s
for s in g:
z,t=m(r[s[0]:s[1]],s[0])
if a<t:a=t;x=z
if a<i:p.remove(h);p+=[(h[0],n[0]),(n[1],h[1])]
elif x[0]<x[1]:p+=[x]
p.sort()
return[(q[0],q[1]-1)for q in p]


Try it online!

Probably still a fair amount of golf left in this, but this is as far as I'm willing to take it for now.

### Explanation

The important realization here was that we can find the maximal $$\k\$$ subarrays iteratively. We start with function m which simply finds the maximal subarray given an array. To find $$\k=1\$$ you simply call m. From here, for any $$\n>0\$$ to find the solution for $$\k=n+1\$$ we start with the solution for $$\k=n\$$. From there we either break one of our subarrays into two, leaving out some negative middle part, add a new subarray, or do nothing. To figure out which is best we run m on all the sections between the subarrays we have and an inverted m on the subarrays we have, and take whichever adds the greatest amount to our total. So the function f simply performs this process $$\k\$$ times, leaving us with the desired result.

### Time complexity

The time complexity is pretty straightforward with this algorithm. Function m is linear with respect to the length of r. For f then, we first note that the size of p never exceeds k, thus for a fixed k things like p.sort() are constant time. So the only two lines that really contribute in f are z,t=m([-a for a in r[s[0]:s[1]]],s[0]) and z,t=m(r[s[0]:s[1]],s[0]) both of which are linear with respect to the length of r, and thus so is f itself.