### Timosh's blog

By Timosh, history, 5 weeks ago,

Hello Codeforces. Recently I faced a problem which I couldn't solve in an hour. It is as follows: Max Sum Subarray of atleast 2 numbers. Of course, for just max sum subarray it is Kadane's algorithm in O(n) time, however, I couldn't think of a way to solve for atleast 2 numbers faster than O(n^2). Any idea or a solution?

UPD: Thanks everyone. Now I know how to solve this problem

• 0

 » 5 weeks ago, # |   0 Its really similar the cses problem https://cses.fi/problemset/task/1644
 » 5 weeks ago, # |   +4 I think this can be done in $O(nlog n)$ time. Consider any subarray: $[l,r]$, then fixing the value of $r$, you want to maximize $(pf[r]-pf[l-1])$, such that $r-l>=1$, or $l <= r-1$. You can iterate over $r$ from $[1,n]$, and store the previous values of $pf[i]$ for all $i$ in $[1,r-2]$. Then you can find the minimum value of $pf[l-1]$ for a given $r$ in $O(logn)$ time, maybe using std::set or something, and update as $ans=max(ans,pf[r]-*s.begin())$. When you are done with $r$, add $pf[r-1]$ to the set of values.
•  » » 5 weeks ago, # ^ |   0 Thanks for the explanation. Anyways, how is this not O(n), as you iterate over r and calculate min of prev prefix and current?
•  » » » 5 weeks ago, # ^ |   +8 The solution I presented is $O(nlogn)$, since I make use of std::set. However, you can use another variable $minv$ such that is represents the minimum of that set. We can update it as follows: $minv=min(minv,pf[r-1])$ once you are done with $r$. Also, you need to keep in mind that for $r=1$, you will not have a solution, since you cannot construct a sub-array of size 2. I'm not familiar with Kadane algorithm but after reading it, I think the idea you have is very similar. Note: you don't update with current $pf[r]$, but with $pf[r-1]$, because you want the length to be at least 2.
 » 5 weeks ago, # | ← Rev. 2 →   +1 Search for a subsegment with a maximum sum without restrictions: you go through the array counting the prefix sum and store the minimum prefix sum on the passed prefix. Let's expand this idea: go through the array, counting the prefix sum and along the way store 2 minimum prefix sums on the passed prefix. By storing 2 minimum values and their indices, you can choose for each prefix i a subsegment of length at least 2, the right boundary of which is equal to i, with the maximum sum. Seems like the right idea
 » 5 weeks ago, # |   +1 Problem on codechefThis question is also similar ,just you need to find the max negative subarray of length minimum 2. O(n) solution of above problem — Code
•  » » 5 weeks ago, # ^ |   0 Yep, sure, the place i got the problem from :)
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Timosh (previous revision, new revision, compare).