Timosh's blog

Max Sum Subarray of atleast 2 numbers
By Timosh, history, 13 days ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Its really similar the cses problem https://cses.fi/problemset/task/1644

→ Reply
»
13 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation. Anyways, how is this not O(n), as you iterate over r and calculate min of prev prefix and current?

    → Reply
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
»
13 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, sure, the place i got the problem from :)

    → Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Timosh (previous revision, new revision, compare).

→ Reply