# Is there a conditional lower bound for the k max subarray sum problem?

Consider an array $$A$$ of integers of length $$n$$. The $$k$$-max subarray sum asks us to find up to $$k$$ (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]$$ for example, then the two subarrays could be $$[2, -1, 2]$$ and $$[2, 2]$$ with total sum $$7$$.

This problem can be solved in $$O(nk)$$ time by a small extension of Kadane's algorithm. I am interested to know if it can be solved faster or if there is a conditional lower bound that implies this might be essentially tight.

One reason the complexity can't be exactly tight is that if $$k=n$$ we can simply find all the positive numbers in the array in linear time.

In "Computing Maximum-Scoring Segments Optimally" by Fredrik Bengtsson & Jingsen Chen the authors describe an $$O(n)$$ algorithm.

• That link takes me to "Credit risk modelling and prediction: Logistic regression versus machine learning boosting algorithms"
– Simd
Feb 4 at 17:44
• I edited to replace the link (with scholar.google.com/…) Feb 4 at 17:56
• @NealYoung there must be a problem as that just adds another step before the wrong link.
– Simd
Feb 4 at 18:05
• Odd. Try following the "All 3 versions" link at the google scholar page. This will take to scholar.google.com/…, which gives several different sources. Do they all fail for you? They work for me. Feb 4 at 18:27
• @NealYoung It must have been my phone browser (chrome) I tried a different browser and it works. Thank you.
– Simd
Feb 4 at 18:33