Output intervals for the optimal subarrays

Question

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

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.