Chef and Subarray : CHEFZOT

Public Submission link: Click here (anyone can submit here )

CU Submission link: Click here (need login by CU account)


Read problems statements in Mandarin Chinese and Russian.

Chef loves research! Now he is looking for subarray of maximal length with non-zero product.

Chef has an array A with N elements: A1A2, …, AN.

Subarray Aij of array A is elements from index i to index jAiAi+1, …, Aj.

Product of subarray Aij is product of all its elements (from ith to jth).

Input

  • First line contains sinlge integer N denoting the number of elements.
  • Second line contains N space-separated integers A1A2, …, AN denoting the elements of array.

Output

  • In a single line print single integer – the maximal length of subarray with non-zero product.

Constraints

  • 1 ≤ N ≤ 100000
  • 0 ≤ Ai ≤ 10000

Sample Input 1 

6
1 0 2 3 0 4

Sample Output 1 

2

Explanation

For the first sample subarray is: {2, 3}.

Sample Input 2 

1
0

Sample Output 2 

0

Explanation

For the second sample there are no subbarays with non-zero product.

Sample Input 3 

3
1 0 1

Sample Output 3 

1

Explanation

For the third sample subbarays is {1}, (the first element, or the third one).


Chef and Subarray Codechef Solution in C

int main(void)
{
    int N,i,j,c,max=0;
    int arr[100000];
    scanf("%d",&N);
    for(i=0;i < N;i++)
    {
        scanf("%d",&arr[i]);
    }
    for(i=0;i < N;i++)
    {
        c=0;
        for(j=i;j < N&&arr[j]!=0;j++,c++)
        {}
        max=((max < c)?c:max);
    }
    printf("%d",max);
	return 0;
}

Chef and Subarray Codechef Solution in C++ 14


int main() {
        int n;
        cin>>n;int c=0;int m=0;
        int a[n];
        for(int i=0;i < n;i++)
        {
            cin>>a[i];
            if(a[i]!=0)
            {
                c=c+1;//cout << c << endl;
            }
            else{
                if(c>m)
                {
                    m=c;//cout << "max:" << m << endl;
                }
                c=0;
            }
        }
        if(c>m)
        {
            m=c;
        }
        cout << m << endl;
	return 0;
}

Chef and Subarray Codechef Solution in Python 3

# cook your dish here
n = int(input())
arr = list(map(int,input().split()))
count=0
j,ans=0,0
while(j < n):
    if arr[j]!=0:
        count+=1

    else:
        ans=max(ans,count)
        count=0
    j+=1
ans=max(ans,count)
print(ans)

Chef and Subarray Codechef Solution in Java

currently not available


Chef and Subarray Codechef Solution
Chef and Subarray Codechef Solution
See also  Mathison and pangrams: MATPAN