# Question
Title: 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.

# Task

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)\\$.

# Answer
> 1 votes
# 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.

---
Tags: code-golf, restricted-complexity
---