1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
+50
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ That link takes me to "Credit risk modelling and prediction: Logistic regression versus machine learning boosting algorithms" $\endgroup$
    – Simd
    Feb 4 at 17:44
  • 1
    $\begingroup$ I edited to replace the link (with scholar.google.com/…) $\endgroup$
    – Neal Young
    Feb 4 at 17:56
  • $\begingroup$ @NealYoung there must be a problem as that just adds another step before the wrong link. $\endgroup$
    – Simd
    Feb 4 at 18:05
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 4 at 18:27
  • $\begingroup$ @NealYoung It must have been my phone browser (chrome) I tried a different browser and it works. Thank you. $\endgroup$
    – Simd
    Feb 4 at 18:33

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.