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
Its really similar the cses problem https://cses.fi/problemset/task/1644
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.
Thanks for the explanation. Anyways, how is this not O(n), as you iterate over r and calculate min of prev prefix and current?
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.
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
Problem on codechef
This question is also similar ,just you need to find the max negative subarray of length minimum 2.
O(n) solution of above problem — Code
Yep, sure, the place i got the problem from :)
Auto comment: topic has been updated by Timosh (previous revision, new revision, compare).