I did this Question using sliding windows by precompute values and deque to get the maximum value

# CHEFSUBA - Editorial

**hikarico**#18

O(n) solution can be done without deques, using frequency table to get the max. Since values are 0 and 1 only, the max value changes by at most 1.

**vdn1999bxvp**#19

Here is my solution: https://www.codechef.com/viewsolution/13634699 as same as author solution but I don’t know why my solution got wrong. Please tell me why I got wrong. Thank you.

**ashishsb95**#20

One question guys!

Is the complexity O(n) for the entire subtask or O(n) for each querie?

**rks_mak**#21

Can someone tell me whats wrong with my code. I would be very greatful.

Submission : https://www.codechef.com/viewsolution/13640002

**abhiroj786**#22

This Solution is giving TLE. I have used Segment Tree/ Range Maximum Query. Please share your insight.

**ashishsb95**#23

A deque approach with window sliding and taking care of k>n condition and array sizes declaration gives an AC.

here is my easy to understand solution easy solution

**tarun_174**#26

can anyone explain this part

else the answer is the maximum sum we can obtain by starting the window from 1 to (n−k+1).

**uddhav_2509**#27

Someone please tell me why my code is giving SIGABRT

https://www.codechef.com/viewsolution/13742388

**rida_doudou**#28

using namespace std;

# include

# define *_* ios*base::sync*with_stdio(false);cin.tie(NULL);

# define D(x) cout<< #x " = "<<(x)<<endl

int main() { *_*

int n;cin>>n; int acum = 0; int ans = 0; int t; for (int i = 0; i < n; ++i) { cin>>t; if (t == 0) { ans = max(ans, acum); acum = 0; } else { acum++; } }

ans = max(ans, acum); cout<<ans<<endl;

return 0; }

**jainsameeksha**#29

I have solved the same problem without using dequeue, segment tree or any sparse table.

I have done it just by checking the contribution of the shifted 1 during the shift if last digit is 1 into the new forward window formed using that new 1 and removing its contribution from the last window formed earlier using that 1 digit. Similar is in case of a 0. To maintain the counts of 1’s in the array used a multiset to store the counts of continuous 1’s in the array after the shift. Answer will be the largest value in multiset whenever query occurs.

Do check once!

https://www.codechef.com/viewsolution/13527132

Thanks

**manasjoshi**#30

Can someone help me with my code, I’m getting WA in 2 test cases - one from small and one from large

I’ve checked the condition for k>n using k = min(k,n).

**potatio**#32

Why do I get a SIGSEV error on exactly one of the testcases? All the others are AC. I used two sliding windows.

**rohitthapliyal**#33

Can anyone reply with side cases and all the test cases you prepared for this problem. I need to run the code on those as its giving a WA.

If anyone is willing to look at the code here is the link: https://www.codechef.com/viewsolution/13789471

The code is simple with no use of special data structures, easy to check.

Thank you in advance

**rohitthapliyal**#34

Now its done. Still gives TLE in 3-4 cases.

Code: https://www.codechef.com/viewsolution/13789884

**sonvar12**#35

My code is giving NZEC in certain cases. Can anyone please help why is this happening?

class CHEFSUBA

{

public static void main(String[] args) throws IOException

{

boolean readFromFile = false;

boolean outputToFile = false;

```
CustomInputOutputClass cio = new CustomInputOutputClass(readFromFile, outputToFile);
int[] temp = cio.readIntegerArrayFromSingleLine();
int n = temp[0];
int k = temp[1];
int p = temp[2];
int[] origArr = cio.readIntegerArrayFromSingleLine();
String queryString = cio.readString();
ArrayList<Integer> answerList = new ArrayList<Integer>();
int length = origArr.length;
int[] arr = new int[2 * length];
int arrLength = 2 * length;
int[] maxArray = new int[arrLength - k + 1];
for(int i = 0; i < 2 * length; i++)
{
arr* = origArr[i % length];
}
for(int i = 0; i < length; i++)
{
int t = arr*;
arr* = arr[2 * length - 1 - i];
arr[2 * length - 1 - i] = t;
}
int count = 0;
for(int i = 0; i < k; i++)
{
count = count + arr*;
}
maxArray[0] = count;
for(int i = 1; i < arrLength - k + 1; i++)
{
maxArray* = maxArray[i - 1] - arr[i - 1] + arr[i + k - 1];
}
/*
for(int x: maxArray)
System.out.print(x + " ");
System.out.println();
*/
Deque<Integer> deque = new LinkedList<Integer>();
for(int i = 0; i < length - k + 1; i++)
{
if(deque.isEmpty())
deque.addFirst(i);
else
{
if(maxArray* < maxArray[deque.getLast()])
deque.addLast(i);
else
{
while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray*)
deque.removeLast();
deque.addLast(i);
}
}
}
//for(int x: deque)
// System.out.print(x + " ");
answerList.add(maxArray[deque.getFirst()]);
count = 0;
for(int i = length - k + 1; i < maxArray.length; i++)
{
if(deque.getFirst() == count)
deque.removeFirst();
if(deque.isEmpty())
deque.addFirst(i);
else
{
if(maxArray* < maxArray[deque.getLast()])
deque.addLast(i);
else
{
while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray*)
deque.removeLast();
deque.addLast(i);
}
}
answerList.add(maxArray[deque.getFirst()]);
count++;
}
//for(int x: answerList)
// System.out.print(x + " ");
count = 0;
for(int i = 0; i < queryString.length(); i++)
{
char query = queryString.charAt(i);
if(query == '?')
System.out.println(answerList.get(count));
else if(query == '!')
count++;
}
cio.cleanup();
}
```

}