<p>In <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C22&amp;q=%22Computing+Maximum-Scoring+Segments+Optimally%22&amp;btnG=" rel="nofollow noreferrer"><em>&quot;Computing Maximum-Scoring Segments Optimally&quot;</em></a> by Fredrik Bengtsson &amp; Jingsen Chen the authors describe an <span class="math-container">$O(n)$</span> algorithm.</p>

CC BY-SA 4.0
2024-02-04T17:44:17.140Z
That link takes me to "Credit risk modelling and prediction: Logistic regression versus machine learning boosting algorithms"
Simd
CC BY-SA 4.0
2024-02-04T17:56:09.217Z
I edited to replace the link (with https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=%22Computing+Maximum-Scoring+Segments+Optimally%22&btnG=)
Neal Young
CC BY-SA 4.0
2024-02-04T18:05:58.740Z
@NealYoung there must be a problem as that just adds another step before the wrong link.
Simd
CC BY-SA 4.0
2024-02-04T18:27:50.623Z
Odd.  Try following the "All 3 versions" link at the google scholar page.  This will take to https://scholar.google.com/scholar?cluster=17449434977220360777&hl=en&as_sdt=0,22, which  gives several different sources.  Do they all fail for you?  They work for me.
Neal Young
CC BY-SA 4.0
2024-02-04T18:33:51.083Z
@NealYoung It must have been my phone browser (chrome) I tried a different browser and it works. Thank you.
Simd
CC BY-SA 4.0
2024-02-04T20:40:04.353Z
@Simd Odd, the link worked for me from the start.
orlp
CC BY-SA 4.0
2024-02-04T17:16:33.923Z
2024-02-04T17:58:17.357Z
2024-02-04T17:58:17.357Z
orlp
<p>Consider an array <span class="math-container">$A$</span> of integers of length <span class="math-container">$n$</span>.  The <span class="math-container">$k$</span>-max subarray sum asks us to find up to <span class="math-container">$k$</span> (contiguous) non-overlapping subarrays of <span class="math-container">$A$</span> with maximum sum.  If <span class="math-container">$A$</span> is all negative then this sum will be <span class="math-container">$0$</span>. If <span class="math-container">$A = [-1, 2, -1, 2, -1, 2, 2]$</span> for example, then the two subarrays could be <span class="math-container">$[2, -1, 2]$</span> and <span class="math-container">$[2, 2]$</span> with total sum <span class="math-container">$7$</span>.</p>
<p>This problem can be solved in <span class="math-container">$O(nk)$</span> time by a small extension of <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem" rel="nofollow noreferrer">Kadane's algorithm</a>.  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.</p>
<p>One reason the complexity can't be exactly tight is that if <span class="math-container">$k=n$</span> we can simply find all the positive numbers in the array in linear time.</p>

<ds.algorithms><lower-bounds>
Is there a conditional lower bound for the k max subarray sum problem?
Simd
# Is there a conditional lower bound for the k max subarray sum problem?

(Asked by: username_0 on 2024-02-01)

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](https://en.wikipedia.org/wiki/Maximum_subarray_problem). 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.

**Tags:** ds.algorithms, lower-bounds


---

## 1 answers

### Answer by username_1 on 2024-02-04. Score: 3 | Accepted answer

In [*"Computing Maximum-Scoring Segments Optimally"*](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=%22Computing+Maximum-Scoring+Segments+Optimally%22&btnG=) by Fredrik Bengtsson & Jingsen Chen the authors describe an $O(n)$ algorithm.

> **Comments:**
> **username_0**: That link takes me to "Credit risk modelling and prediction: Logistic regression versus machine learning boosting algorithms"  
> **username_2**: I edited to replace the link (with https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=%22Computing+Maximum-Scoring+Segments+Optimally%22&btnG=)  
> **username_0**: @NealYoung there must be a problem as that just adds another step before the wrong link.  
> **username_2**: Odd.  Try following the "All 3 versions" link at the google scholar page.  This will take to https://scholar.google.com/scholar?cluster=17449434977220360777&hl=en&as_sdt=0,22, which  gives several different sources.  Do they all fail for you?  They work for me.  
> **username_0**: @NealYoung It must have been my phone browser (chrome) I tried a different browser and it works. Thank you.  
> **username_1**: @username_0 Odd, the link worked for me from the start.  

---

