Given an array, print the largest subarray that has elements in an increasing order

Question

Sid · Accepted Answer

Algorithm:
Lets say the input array is:
1 2 3 -4 4 5 6 7 8 9 0
1. Start with the first element and keep on increasing the count and index till you hit an element that is less than the previous element. In the above case -4 < 3, hence count =3, so store it in maxCount and LastIndex = index + 1 - count
So, until this point 1 2 3 is the largest subarray.
2. Again start from -4, with index = 3 and count = 0 and keep on increasing the index and count till you hit an element which is less than the previous element. Here 0 < 9, hence you stop and compare the new count with the maxCount to see which is greater. Similarly, keep on following this till you hit the end of the array.

Complexity - O(n)

Anónimo · Answer

Sid's solution is not for longest increasing subsequence problem
the best answer would be O(nlgn)

Eagle · Answer

We only need the longest contiguous subsequence, so it can be done in linear time like in Sid's solution.

Anónimo · Answer

This is dynamic programming

light · Answer

B: really?, it has an O(n) solution.

def conseq(arr):
   cur_start,cur_end,cur_size=0,0,1
   max_start,max_end,max_size=0,0,0

   n=len(arr)
   if n==0: return (0,0,0)

   for i in range(1,n):
     if arr[i]>arr[i-1]:
       cur_size+=1
       cur_end=i

     else:
        cur_start=i
        cur_end=i
        cur_size=1

     if cur_size> max_size:
       max_size=cur_size
       max_start=cur_start
       max_end=cur_end
   return (max_size,max_start,max_end)

SP · Answer

All the above answers are incorrect except the one that pointed out it's an instance of Longest Increasing Subsequence. The standard dynamic programming algorithm is O(n^2). There is a more complex solution that runs in O(n lg n). Google for the answers.

B · Answer

Classic NP problem. No easy solution for this. Time complexity could be very high

Anónimo · Answer

Pretty easy really

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo