Alternating subarray prefix

There's an array A consisting of N non-zero integers A1..N. A subarray of A is called alternating if any two adjacent elements in it have different signs (i.e. one of them should be negative and the other should be positive).

For each x from 1 to N, compute the length of the longest alternating subarray that starts at x - that is, a subarray Ax..y for the maximum possible y ≥ x. The length of such a subarray is y-x+1.

Input

The first line of the input contains an integer T - the number of test cases.
The first line of each test case contains N.
The following line contains N space-separated integers A1..N.

Output

For each test case, output one line with N space-separated integers - the lengths of the longest alternating subarray starting at x, for each x from 1 to N.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 105
-109 ≤ Ai ≤ 109

Sample 1:

Input

Output

3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3

1 1 1 1
4 3 2 1
1 1 3 2 1 1

Explanation:

Example case 1. No two elements have different signs, so any alternating subarray may only consist of a single number.

Example case 2. Every subarray is alternating.

Example case 3. The only alternating subarray of length 3 is A3..5

Solution:-

#include <stdio.h>

int main() {
    int t, n, i;
    int a[100009];
    int len[100009];
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        len[n - 1] = 1;
        for (i = n - 2; i >= 0; i--) {
            if (a[i] * (long long)a[i + 1] < 0) { // Casting to long long for multiplication to avoid overflow
                len[i] = len[i + 1] + 1;
            } else {
                len[i] = 1;
            }
        }
        printf("%d", len[0]);
        for (i = 1; i < n; i++) {
            printf(" %d", len[i]);
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        vector<int> a(n), len(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        len[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (a[i] * (long long)a[i + 1] < 0) {
                len[i] = len[i + 1] + 1;
            } else {
                len[i] = 1;
            }
        }
        cout << len[0];
        for (int i = 1; i < n; i++) {
            cout << " " << len[i];
        }
        cout << endl;
    }
    return 0;
}

}for _ in range(int(input())):

    n=int(input())
    ints=list(map(int,input().split()))
    
    ans=[0]*n
    ans[-1]=1
    j=0
    # for j in range(size-1):
    while(j<n-1):
        # m_count=1
        count=1
        for i in range(j,n-1):
            if(ints[i]<0):
                if(ints[i+1]>0):
                    count+=1
                else:
                    # If both ints are having same sign then, just compare with m_count and
                    # update it
                    # if(count>=m_count):
                    # m_count=count
                    break
            else:
                if(ints[i+1]<0):
                    count+=1
                else:
                    # Same sign so, now check and update
                    # if(count>=m_count):
                    # m_count=count
                    break
        itr=count
        while(itr>0):
            ans[j]=itr
            j+=1
            itr-=1
            
    print(*ans)

Header Ads Widget

Alternating subarray prefix | codechef solution