3
\$\begingroup\$

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

\$\endgroup\$
8
  • 1
    \$\begingroup\$ You should put \$k\leq3\$ in bold, and probably also a bit higher, as it's quite significant. \$\endgroup\$ Feb 2 at 15:09
  • \$\begingroup\$ @CommandMaster Thank you. \$\endgroup\$
    – Simd
    Feb 2 at 15:11
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Feb 2 at 16:08
  • \$\begingroup\$ @CursorCoercer you can 1 index but other than that please stay with the way I have done it. \$\endgroup\$
    – Simd
    Feb 2 at 16:11
  • \$\begingroup\$ Shouldn't the first example have for k=2 the subarray containing 1? \$\endgroup\$
    – qwr
    Feb 6 at 19:26

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Very cool answer \$\endgroup\$
    – Simd
    Feb 5 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.