Find count of alternating numbers

Question

What I am trying to do is to find count of alternating numbers such that it alternates with -ve and positive sign for e.g.: 1 -2 3 -4 would get me 4 3 2 1 as from 1 to -4 including the two numbers there are 4 numbers. Similarly, for 1 1 -3 2 would get me 1 3 2 1. Now I have the code but I cannot optimise it and it returns me a time limit exceeded error even though it works for moderate input stream.

Here, alternating means like first number is positive and second number is negative and next number is positive and so on. So if input is 1 -2 3 -4 then from number 1 maximum I can travel to -4 such that there is an alternating sequence. So the count =3 numbers + the number itself i.e 4. Again from -2 if I travel from I can go till -4 as it alternates from negative positive and negative. So it is 2 numbers +1=3 again. Similarly, for r=each position I get it as 4 3 2 1. Now suppose number is 1 1 -3 2 then there is no number for 1 to find the next alternating number immediately so 1.

So for 1 1 -3 2 for 1 since there is no immediate -ve number it is a 1.For the second 1 I can traverse to a -3 and 2 i.e 2 number so count=2+1=3.For -3 all I find is a single 2 so count is 1+1=2.For the last number it is 1.So the answer is 1 3 2 1

Sample input: 1 -2 1 -3 2

Output: 4 3 2 1

j=0
count=0
length=(raw_input())
st=map(int,raw_input().split())
while j+1 < len(st):
     k=j+1
     count=0
     temp=j
     while k<len(st) and ((st[k]<0 and st[j]>0) or (st[k]>0 and st[j]<0)):
       count+=1
       k+=1
       j+=1
     print count+1,
     j=temp+1
print 1

Answer 1

This problem is much easier looking it backwards: Instead of processing the input in the order given, process it in reverse order. You know the last number in your answer will be 1, because no numbers follow it. Now the previous one could be a 2 if the sign is different with the last one or a 1 if its the same sign.

So basically, each step back can either add 1 to the list of consecutive numbers with alternating signs or reset the count to 1.

The code:

    length=(raw_input())
    st = map(int,reversed(raw_input().split()))

    answ = []
    count = 0
    for i, num in enumerate(st):
         count += 1
         if i > 0 and (num < 0) == (st[i - 1] < 0):
            count = 1
        answ.append(str(count)) 

    print " ".join(reversed(answ))  

Answer 2

Are you sure you should print intermediate results of just final answer? If the final is enought then there is no reason to return back to initial j after inner loop and complexity of algorithm become O(n):

j = 0
max = 0
length = (raw_input())
st = map(int,raw_input().split())
while j+1 < len(st):
   k = j + 1
   count = 1
   while k<len(st) and ((st[k]<0 and st[k-1]>0) or (st[k]>0 and st[k-1]<0)):
     count += 1 
     k += 1
     j += 1
   for c in range(1, count+1)[::-1] :
     print c
   j += 1