You are not logged in. Please login at www.codechef.com to post your questions!

×

MMSUM - Editorial

11
6

PROBLEM LINK:

Contest
Practice

Author: Sergey Kulik
Testers: Kevin Atienza and Vasya Antoniuk
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Easy

PREREQUISITES:

Maximum Subarray Sum

PROBLEM:

Given an array $A[1\ldots N]$, what is the maximum subarray sum you can get by removing at most one element?

QUICK EXPLANATION:

For every position $i$, compute the maximum subarray sum that ends in position $i$. Call it $E[i]$.
For every position $i$, compute the maximum subarray sum that starts in position $i$. Call it $S[i]$.

Both can be done in $O(N)$ using Kadane's algorithm/dynamic programming.

The answer is the largest among the following values:

  • The maximum in $E$.
  • The maximum $E[i-1] + S[i+1]$ for every position $1 < i < N$.

EXPLANATION:

No removals

Let's first answer a simpler question: What is the maximum subarray sum of the array (without any removals)? This is actually a standard problem and you might already be familiar with it, but let's describe it anyway.

Here's a naïve solution (in pseudocode):

answer = -INFINITY
for j=1..N:
    current = 0
    for i=j..1 by -1:
        current += A[i]
        answer = max(answer, current)

It simply tries out all subarrays. Unfortunately, this is slow; it runs in $O(N^2)$ time, and for $N \approx 10^5$ this will not pass the time limit.

To improve this solution, notice that we don't have to check all the subarrays that end at $j$. We can classify all such subarrays into two types: whether it has length $1$ or length greater than $1$.

  • If it has length $1$, then the sum is simply $A[j]$.
  • If it has length greater than $1$, then we can break this subarray into two parts. The first part is a subarray that ends in $j-1$, and the second is $A[j]$ itself. Thus, in order to maximize the sum, we must choose the subarray that ends in $j-1$ with the maximum sum.

That last part is crucial; if you study the code above more closely, notice that what we're computing is, for every possible rightmost index $j$, the maximum subarray sum that ends in $j$. And we're doing this in increasing order of $j$. Thus, when we're trying to compute it for $j$, we already have the answer for $j-1$, so we don't need a loop any more!

The following code illustrates it better:

answer = -INFINITY
current = 0
for j=1..N:
    current = max(A[j], current + A[j])
    answer = max(answer, current)

Notice that before the line current = max(A[j], current + A[j]), the variable current contains the maximum sum that ends in $j-1$. Thus, current + A[j] is the maximum sum of any subarray that ends in $j$ with length greater than $1$.

This is now much faster: it runs in $O(N)$ time! Also, if you're curious, this algorithm is actually famous and has a name: Kadane's algorithm.

Implementation notes:

  • Note that $\left|A[i]\right|$ can reach up to $10^9$, so current and answer will exceed the bounds for 32-bit integers. So you should use 64-bit variables (long long in C/C++, long in Java).
  • For INFINITY, you can use a very large number that will exceed all finite numbers under consideration. Since the maximum absolute sum is only $10^5\cdot 10^9 = 10^{14}$, an INFINITY value of, say, $10^{18}$ is good enough for our purposes!

One removal

Now, let's answer the original problem, where you are allowed to remove at most one element from the array. We already know the answer when you don't remove any element, so all that remains it to compute the answer if we remove exactly one element. The maximum among these two is the answer. More specifically,

  • Let $M_0$ be the answer if you don't remove any element, and
  • Let $M_1$ be the answer if you remove one element.

Then the answer is $\max(M_0, M_1)$. We already know $M_0$ from above, so all that remains is computing $M_1$.

Obviously, we can try removing each element in turn, and computing the maximum subarray sum, and obtaining $M_1$ as the maximum among all these maximums. But this takes $O(N^2)$ time which is too slow. We will need a better algorithm.

Suppose we remove the element $A[i]$. Then there are only three possible cases for the maximum subarray sum:

  • The maximum subarray is completely to the left of $A[i]$.
  • The maximum subarray is completely to the right of $A[i]$.
  • The maximum subarray contains $A[i-1]$ and $A[i+1]$.

But here's an important observation: in the first two cases, the subarrays are actually also subarrays of the original array, which means their sums cannot be more than $M_0$. And since we're trying to maximize the answer and we alreaady know that the answer is $\ge M_0$, we can safely ignore these cases!

So all that remains is computing the maximum sum of any subarray that contains $A[i-1]$ and $A[i+1]$ (ignoring $A[i]$ of course). We can decompose such a subarray into two parts:

  • A subarray that ends in $A[i-1]$, and
  • A subarray that starts at $A[i+1]$.

These two subarrays don't overlap, so in order to maximize the sum, we want to maximize them individually. But we have already computed all maximum subarray sums that end in every position, from the previous algorithm! So if we just store the partial results that we got, then we can answer the first part quickly!

In more detail, let $E[i]$ be the maximum subarray sum that ends in $A[i]$. We can compute $E[1\ldots N]$ using the previous algorithm:

answer = -INFINITY
current = 0
for j=1..N:
    current = max(A[j], current + A[j])
    answer = max(answer, current)
    E[j] = current

Similarly, we can define $S[i]$ to be the maximum subarray sum that starts at $A[i]$. Computing $S[1\ldots N]$ by performing the algorithm in reverse, as in the following:

current = 0
for j=N..1 by -1:
    current = max(A[j], current + A[j])
    answer = max(answer, current)
    S[j] = current

With arrays $S[1\ldots N]$ and $E[1\ldots N]$, we can now compute the maximum sum of any subarray that contains $A[i-1]$ and $A[i+1]$, assuming $A[i]$ is removed: It is simply $E[i-1] + S[i+1]$!

for i=2..N-1:
    answer = max(answer, E[i-1] + S[i+1])

By combining all these snippets, we now have the answer to the problem!

Time Complexity:

$O(N)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester
Editorialist

This question is marked "community wiki".

asked 27 May '16, 07:32

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 06 Jun '16, 13:52

admin's gravatar image

0★admin ♦♦
19.8k350498541


This algorithm doesn't work on n=2

link

answered 01 Jun '16, 04:27

cc15's gravatar image

2★cc15
112
accept rate: 0%

Setter and tester solutions are for the problem Kitchen Timetable (KTTABLE)

link

answered 31 May '16, 22:01

krutarthkp800's gravatar image

4★krutarthkp800
334
accept rate: 0%

I tried the same but the solution given is not working.......Is it for the same problem.....i doubt....???????

link

answered 31 May '16, 22:21

sh1wet11_1995's gravatar image

2★sh1wet11_1995
1
accept rate: 0%

Can this problem be solved using divide and conquer?
Tried,but then got WA.

link

answered 31 May '16, 22:40

ansh1star033's gravatar image

3★ansh1star033
206129
accept rate: 9%

Please Help me with this ! this is the algorithm applied

1)eliminate one element at a time in the array
2) correspondingly find the maximal sub array sum (by the standard algorithm) 3) store it in another array
4)sort this array and print the last(largest) element.

LINK OF MY SOLUTION:-https://www.codechef.com/viewsolution/10256324

link

answered 01 Jun '16, 01:05

vidit_123's gravatar image

2★vidit_123
1036
accept rate: 5%

edited 01 Jun '16, 01:09

according to your algorithm for Test case n=5 input 1 -2 3 -2 5 output will be 12

link

answered 01 Jun '16, 07:42

rajaryan1990's gravatar image

2★rajaryan1990
1
accept rate: 0%

This can be done in just 1 loop with O(1) space cost by adapting Kadane's method, rather than requiring 3 loops and O(n) (additional) space cost as in the solution shown by setter/tester.

Example https://www.codechef.com/viewsolution/10259181 which is a simplified version of https://www.codechef.com/viewsolution/10214880

link

answered 01 Jun '16, 09:32

godmar's gravatar image

2★godmar
1
accept rate: 0%

We have to modify this logic for i=2..N-1: answer = max(answer, E[i-1] + S[i+1])

As for(i=1;i<=N;i++{ if(i-1<1){ answer = max(S[i+1],answer); }else{ if(i+1==N+1){ answer=max(answer,E[i-1]); }else{ answer=max(answer,E[i-1]+S[i+1]; }

} then it will work for N=2 as well.

}

link

answered 01 Jun '16, 09:47

rajaryan1990's gravatar image

2★rajaryan1990
1
accept rate: 0%

@godmar, I too applied the same algorithm and ended up doing it in a single pass. Link to the solution

link

answered 01 Jun '16, 12:01

vjvishjn's gravatar image

3★vjvishjn
312
accept rate: 0%

It doesn't seem to give the correct answer.

link

answered 01 Jun '16, 12:02

partha2717's gravatar image

3★partha2717
1
accept rate: 0%

link

answered 01 Jun '16, 13:55

karbish98's gravatar image

2★karbish98
191
accept rate: 0%

Alternate solution: Got AC Slightly different from editorial. Keep two arrays dpWithDelete and dpWithoutDelete which keep track of the MaxSum with and without delete. Link https://www.codechef.com/viewsolution/10193855

Please approve.

link

answered 01 Jun '16, 14:16

salgarkarap's gravatar image

2★salgarkarap
1
accept rate: 0%

edited 01 Jun '16, 14:18

calculate two array forward and backward which store the current maximum sum till that index .and now for any index calculate backward[i+1]+forward[i-1] for that index .which indicates the maximum sum for that index if that particular index value is not used.. and you have to store maximum value in a variable (which indicate if no element of array is remove)..

link to solution:https://www.codechef.com/viewsolution/15065218

link

answered 21 Aug '17, 19:37

ayushpatidar's gravatar image

4★ayushpatidar
11
accept rate: 0%

@vijju123 @admin

DIFFICULTY: Easy, But this question has tag Medium. Plz. look into this.

link

answered 01 Mar '18, 03:20

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

answer = -INFINITY current = 0 for j=1..N: current = max(A[j], current + A[j]) answer = max(answer, current) E[j] = current

Here E[j] = current is given, I am having doubt why it's not E[j] = answer as till i answer is the maximum subarray sum

link

answered 13 Mar, 19:41

sanjay_panchal's gravatar image

2★sanjay_panchal
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,875
×2,658
×55
×20

question asked: 27 May '16, 07:32

question was seen: 10,786 times

last updated: 13 Mar, 19:41