I have a doubt.
Consider the given array
2 2 1 2 2 1 2 2 1 2 2 2 2 2 2
here the prefix sum of the largest subarray with 1st and last number 1 is 11.
but z=18 is reachable which is greater than 11 and even which seems to be an counterexample to above solution.
Could you please clarify if i am getting it right.
Tester’s solution is incorrect!
1
5
2 2 1 2 1
Returns 7. The correct answer is 8.
Here is the proof for S−min(C1,C2)
We observe that if we get 1 2 2 2 or 1 2 2 1 1 2 or 2 2 1 2 1 i.e. any subarray which is starting or with ending with 1 we can make every number till its sum.
Now, if we see in this 2 2 1 2 2 1 1 2 all possible numbers till prefix sum at 7 is possible. While after that it won’t be possible. Also we can consider that all numbers till suffix sum at 3 is possible. While before that it won’t be possible. Because of each 2 we won’t be able to make a number.
Hence, with other examples it can be shown that we need to know number of 2’s just before first occurrence of 1 either from left or right side whichever is optimal and subtract it from total sum.
2 Likes
Actually while implementing the solution we need first check one thing ,whether the array is starting with 1 or ending with 1 .If the answer is “YES” we need to print the sum of the array straight forward.If the answer is “NO” we need compute the answer using the above method.Just be aware of otherwise you might get wrong answers while solving it.( although the editorialist mentioned this many people tend to forget this point)
1 Like
I can’t proof this but it got an AC.
if array has only twos:
ans= sum/2
else if array starts and ends with 2:
ans= sum-1
else
ans=sum
Here’s my solution.
If C_1 and C_2 in S-min(C_1, C_2) are the number of consecutive 2 s on the left and on the right end respectively then this formula holds true even if there are no 1 s in the array (all the array elements are equal to 2).
All sub-array sums are in the range 1..S. If we only consider the set of prefix sums then for any X in that range either X or X+1 belongs to the set. If the array starts with 1 consider the set of sums of all sub-arrays that start from the second position. For any X from the range 1..S X is either equals to one of these sums or one of the prefix sums, so that the set of all sub-array sums fills the entire range. The same is true when the array ends with 1.
If our array contains a sub-array with sum s that starts or ends with 1 then the set of sums of all sub-arrays is guaranteed to contain the range 1..s. What is the largest sum sub-array that starts or ends with 1? One end of this sub-array is 1 that is closest to an array end, and the other - the opposite end of the array. Let C = min(C_1, C_2). Then the size of this sub-array is N - C. All sub-arrays of this size contain all the 1 s of the entire array and have the same sum S - 2C. Sub-array with a larger sum is of a larger size, it also contains all the 1 s of the entire array, its sum depends only on its size, which increases by 2 if the size increases by 1. So we have S - 2C consecutive values for sub-array sizes up to N-C following by C values in increments of 2 for sizes up to N (S - C total).
Seems like you misunderstood my statement.
I meant, either starting with, or ending with. Both are not necessary. In your example, the largest sub-array starting or ending with 1 has sum 23. Only values 24 and 26 are unreachable.
okay.Got it.Thanks
answer is 8 that’s true
I think we do not need to check this case specially. Though no harm mentioning 
Well, i think we’ll have to wait for admin statement.
update ur solution as-- if array has only twos: ans=sum/2
1 Like
for second line, for test case 2 2 1 2 2 output is 7 because 6 and 8 can not be made… but according to ur second point, ans=sum-1 so it would be 9-1=8 but ans is 7… i am getting confused
exactly…
i think ur approach is wrong…
actual answer will be sum-min(c1,c2) where c1 is no of 2’s before leftmost 1 and c2 is no of 2’s after rightmost 1
I understood what the right solution should be. I think the test cases were not strong enough.
If you got an AC then your solution is likely to be wrong as the tester’s solution is.